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的位置.
保证答案≤1e10,且一定存在.
Input
第一行一个数t,表示测试数据的组数,后面t行,每行两个数d,k
Output
输出共t行,对于每组输入数据的答案
Sample Input
1
1 201103
Sample Output
661290