Problem Description

有一个矩阵方程$xA=B$,其中$x$是一个$1*n$的行向量,$A$是一个$n*n$的矩阵,$B$是一个$1*n$的行向量,并且$n=9999999999999999999$.

并且$A[i][j]=1$当且仅当$i$是$j$的约数,否则$A[i][j]$是$0$,$B[i]=1$当且仅当$i=1$,否则$B[i]$是$0$.

给出一个$d$和一个$k$,求$x$中第$k$个数值恰好是$d$的位置.

保证答案$\leq 1e^{10}$,且一定存在.

Input

第一行一个数$t$，表示测试数据的组数，后面t行，每行两个数$d,k$

Output

输出共$t$行，对于每组输入数据的答案

1
1 201103

661290