题目背景

CYJian 班的这个队形……是梯形么？？

$\color{white}\text{信息竞赛班的女生能有多少??}$

题目描述

教官觉得 CYJian 班上的队形不是很美观很不美观，所以教官决定要重排一下队形。

教官先让所有同学按照学号排好序站成一列，然后每一次把当前队列第 $1, 2, 3, 5, 8, 13, \cdots$（差不多就是斐波那契数列了）个人拉出来，直到没有人能拉出来为止，然后这些人组成一行，排到上一行的后面。

举个栗子，如果一共有 $10$ 个人，大概就是这样子的（加粗表示当前选到的人）：

1. $\bm{\color{red}1}\ \bm{\color{red}2}\ \bm{\color{red}3}\ 4 \ \bm{\color{red}5} \ 6 \ 7 \ \bm{\color{red}8} \ 9\ 10$，取走后：$4\ 6\ 7\ 9\ 10$；
2. $\bm{\color{red}4}\ \bm{\color{red}6}\ \bm{\color{red}7}\ 9\ \bm{\color{red}10}$，取走后：$9$；
3. $\bm{\color{red}9}$。

最后的队形长这样:

• 第一行：$1\ 2\ 3\ 5\ 8$；
• 第二行：$4\ 6\ 7\ 10$；
• 第三行：$9$。

（教官排的队形当然得说好看了……）

我们现在定义一行的美观度为这一行所有人学号的乘积能分解的质因子的个数（特别的，$1$ 分解质因子不能得到任何质因子，所以个数为 $0$）。

比如第二行，$4 \times 6 \times 7 \times 10=1680=2 \times 2 \times 2 \times 2 \times 3 \times 5 \times 7$，所以该行美观度为 $7$。

年级一共有 $T$ 个班级，每一个班级都要排一次队形。现在给出第 $i$ 个班级人数 $N_i$ 和一个正整数 $K_i$，需要你求出第 $i$ 个班级排队形后第 $K_i$ 行的队伍的美观度。

特别的，如果排的队形中没有第 $K_i$ 行则输出 $-1$。

输入格式

第一行一个正整数 $T$。

接下来 $T$ 行每行两个正整数 $N_i$ 和 $K_i$。

变量的意义详见题面描述。

输出格式

$T$ 行，每行一个正整数表示所求的美观度。

3
10 2
12 2
1 2

7
7
-1

提示

本题采用捆绑测试。

• Subtask 1（30pts）：$K_i = 1$，$1 \le N_i, T \le 1000$；
• Subtask 2（30pts）：$1 \le K_i \le 100$，$1 \le N_i \le 10000$，$1 \le T \le 5000$；
• Subtask 3（40pts）：$1 \le K_i \le 10000$，$1 \le N_i \le 5 \times 10^6$，$1 \le T \le 10^6$。

数据不保证存在全是 $-1$ 的测试点。