如今，双因素身份验证（即用户需要使用主密码以及一个或多个一次性密码）正变得越来越普遍。考虑生成此类密码的一种可能方式。

令 $F(Q)$ 为不超过 $Q$ 的正整数中，可以表示为 $2^x - 2^y$（其中 $x, y$ 为非负整数）的数的个数。考虑所有满足 $F(Q) = N$ 的数 $Q$，并按照它们二进制表示中“1”的个数进行升序排序。如果两个数二进制表示中“1”的个数相同，则按数值大小进行比较。所提出的算法将选择该排序序列中的第 $K$ 个数。

你需要为 $T$ 次身份验证会话找到一次性密码。

输入格式

第一行包含一个整数 $T$ —— 身份验证会话的数量。接下来的 $T$ 行，每行包含两个数字 $N_i$ 和 $K_i$ —— 一次性密码生成算法的参数。

$1 \le T \le 10^5$ $1 \le N_i, K_i \le 10^{18}$

输出格式

输出 $T$ 行，每行包含一个整数 —— 对应身份验证会话的一次性密码。每个密码应模 $10^9 + 7$ 输出。如果无法生成一次性密码，则输出 -1。

样例

样例输入 1

1
16 10

样例输出 1

42