排队

$CYJian$班的这个队形...是梯形么?? $\color{white}\text{信息竞赛班的女生能有多少??}$

教官觉得$CYJian$班上的队形~~不是很美观~~很不美观..所以教官决定要重排一下队形.. 教官先让所有同学按照学号排好序站成一列,然后每一次把当前队列第1,2,3,5,8,13...(差不多就是斐波那契数列了..)个人拉出来,直到没有人能拉出来为止..然后这些人组成一行,排到上一行的后面.. 举个栗子,如果一共有10个人,大概就是这样子的:(加粗表示当前选到的人) 1: **1** **2** **3** 4 **5** 6 7 **8** 9 10 取走后: 4 6 7 9 10 2: **4** **6** **7** 9 **10** 取走后: 9 3: **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 \rightarrow 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$($30$ $pts$): $ K_i = 1, 1 \leqslant N_i, T \leqslant 1000 $ $Subtask$ $2$($30$ $pts$): $ 1 \leqslant K_i \leqslant 100 \ \ \ \ 1 \leqslant N_i \leqslant 10000 \ \ \ \ 1 \leqslant T \leqslant 5000 $ $Subtask$ $3$($40$ $pts$): $ 1 \leqslant K_i \leqslant 10000 \ \ \ \ \ 1 \leqslant N_i \leqslant 5*10^6 \ \ \ \ \ 1 \leqslant T \leqslant 10^6 $ 数据不保证存在全是-1的测试点.. 注意:**本题捆绑测试**