寻找整数

题目描述

给定整数$m$,$k$，求出正整数$n$使得$n+1$,$n+2$,$\ldots$,$2n$中恰好有$m$个数在二进制下有$k$个$1$。有多组数据。

输入格式

第一行一个整数$t$表示数据组数。

接下来$t$行每行两个整数$m$,$k$。

输出格式

每组数据输出一行两个整数，第一个数表示$long$ $long$范围内任意一个满足条件的$n$，第二个数表示满足条件的$n$的个数（无穷多用$-1$表示）。

保证$10^{18}$以内存在满足条件的$n$。

如果每组数据第一个数全部正确，得$4$分。

如果每组数据第二个数全部正确，得$6$分。

数据范围与提示

• 对于$10\%$的数据，$k = 2$；
• 对于$20\%$的数据，$k \leq 3$；
• 对于另外$50\%$的数据，保证满足条件的$n$均在$10^{18}$以内；
• 对于$100\%$的数据，$1 < t < 2000$，$0 \leq m \leq 10^{18}$，$1 \leq k \leq 64$。

样例

1
1 2

2 1

见number2.in

见number2.out