题目背景

$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的测试点..

注意:本题捆绑测试