先来找些性质：
- \(A\) 中最小的元素 \(M\) 肯定是最小的不是 \(S\) 的因子的数，由于 \(\text{lcm}(1,2,3,\cdots,43)>10^{18}\)，所以 \(M\le 43\)。
- 对于每个 \(0\le i<M\)，\(\bmod M=i\) 的数被选择的部分必然是一段后缀，因为如果你选择了 \(M\) 选择了某个 \(\bmod M=i\) 的数 \(v\)，那么再选 \(v+M\) 也是不会有影响的。
- 考虑扩展得到最优解对应的 \(A\) 的过程，必然是我从 \(A=\{M,2M,3M,\cdots,\lfloor\dfrac{S-1}{M}\rfloor·M\}\) 开始，每次找到最小的满足”加入这个数以后得不到 \(S\)“的数 \(v\)，将 \(v,v+M,v+2M,\cdots\) 加入 \(A\)。
现在考虑如何求解答案。由于我们暴力扩展最多只会扩展 \(M-1\) 轮，所以我们可以暴力求出每次要加入的数 \(\bmod M\) 的值，这一脸同余最短路的样子，具体来说我们实时维护个 \(mn_i\) 表示 \(\bmod M=i\) 的数当中最小的能够表示为 \(A\) 中数的线性组合的数，这样我们可以在 \(O(M)\) 的时间内算出 \(\bmod M=i\) 的数当中最小的满足加入这个数之后 \(S\) 不能被表示出来的数。这样我们求出了每个 \(\bmod M\) 的等价类最小的在 \(A\) 中的数，直接二分求第 \(k\) 小即可。
时间复杂度 \(O(TM^3)\)。
const ll INF=0x3f3f3f3f3f3f3f3fll;
ll S,K,mn[45],val[45];int m;
ll calc(ll p){
ll sum=0;
for(int i=0;i<m;i++)if(val[i]<=p)sum+=(p-val[i])/m+1;
return sum;
}
void solve(){
scanf("%lld%lld",&S,&K);for(int i=2;;i++)if(S%i){m=i;break;}
memset(mn,63,sizeof(mn));memset(val,63,sizeof(val));mn[0]=0;val[0]=m;
while(1){
int rem=0;ll mnv=INF;
for(int i=1;i<=m-1;i++){
if(val[i]!=INF)continue;ll mx=i;
for(int j=1;j<=m-1;j++){
int nd_rem=(S-j*i%m+m)%m;
if(mn[nd_rem]!=INF)chkmax(mx,(S-mn[nd_rem]+j)/j);
}
while(mx%m!=i)++mx;
if(mx<mnv)mnv=mx,rem=i;
}if(mnv==INF)break;val[rem]=mnv;
for(int i=1;i<=m-1;i++){
if(1ll*i*mnv>S)break;
for(int j=1;j<=m-1;j++){
int nd_rem=(j-(mnv%m)*i%m+m)%m;
chkmin(mn[j],mn[nd_rem]+i*mnv);
}
}
}
if(calc(S-1)<K)return puts("-1"),void();
else{
ll L=1,R=S-1,P=0;
while(L<=R){
ll mid=L+R>>1;
if(calc(mid)>=K)P=mid,R=mid-1;
else L=mid+1;
}printf("%lld\n",P);
}
}
int main(){
int qu;scanf("%d",&qu);while(qu--)solve();
return 0;
}