Description

小A很喜欢研究数列，尤其是幂级数和其他序列的关系。

幂级数是一类最简单的函数项级数，从某种意义上说，从某种意义上说，它也可以看作是多项式函数的延伸，幂级数在理论和实际中都有很多应用。

老师给小A描述了一个问题，给定一个幂级数 $A$ 的分解项 $A'$ 和随机 $01$ 序列 :

$A=\sum^{+\infty}_{n=0}x^n = x^0 + x^1 + x^2 + \cdots + x^n + \cdots$

$A'=[x^0, x^1, x^2, \cdots, x^n, \cdots]$

$B=[y_0, y_1,y_2,\cdots,y_n,\cdots], y_i=0,1$

问题的内容是给定两个整数 $x$ 和 $k$，将上述两序列看为两个 $n$ 维向量，因为 $B$ 向量有任意性，但是不可以是全0向量，所以要求找到 $A'\cdot B$（两向量点乘结果为一个数值）从小到大的第 $k$ 个元素的值。

因为第 $k$ 个元素值可能过大，所以要求使结果对1000000007取模。

​点乘​：对于两向量 $a = [a_1, a_2], b = [b_1, b_2]$， 点乘公式为 $a\cdot b = a_1 \times b_1 + a_2 \times b_2$ ，要求运算向量长度相等。

Input Format

每组测试包含多个测试用例。第一行包含 $t(1 \le t \le 10^4)$ 测试用例数量 ，下面是测试用例的描述。

每个测试用例一行，包含两个整数 $x, k(2\le x \le 10^9, 1\le k \le 10^9)$。

Output Format

对于每个测试样例，输出两向量点乘的从小到大的第 个值。

3
4 5
2 3
123 123​

17
3
209771727​

Hint

Note

解释第一个样例：

$x = 4$

$A'\cdot B$ 后可以组成的数字由小到大是 $[1, 4, 5, 16, 17]$，所以答案输出17