该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

2025 年的最后一天，一只羊正在为即将到来的 2026 新年庆典准备礼物。

回顾过去的一年，一只羊发现生活中充满了像“积性函数”原本错综复杂的关系：莫比乌斯函数 $\mu(n)$ 的反演、欧拉函数 $\varphi(n)$ 的循环、约数个数 $\tau(n)$ 的纠葛。这些函数虽然性质优美，但往往需要互素的条件才能拆分，就像过去一年中那些必须要特定条件才能达成的目标，让人感到些许疲惫。

“新的一年，应该是简单而纯粹的。” 一只羊看着窗外的烟火嘟囔着。

一只羊希望 2026 年的幸福感不再受复杂的互素条件限制，而是像完全加法函数一样：无论什么情况，幸福都能直接叠加。不需要 $\gcd(m,n)=1$ 的束缚，哪怕是两个相关的事件，快乐也能简单地相加，$f(mn)=f(m)+f(n)$。

“‘积性’意味着纠缠，我不想再把快乐乘在一起了！” 一只羊合上旧的日历，决定在新的一年研究完全加法函数。为了测试这种“简单的幸福”是否存在，一只羊定义了一个评估数值，准备用一道题来寻找那些表里如一的“幸运数”……

题目描述

设 $f:\mathbb{Z}_{>0}\to\mathbb{Z}$ 为一个完全加法函数，即对所有正整数 $m,n$ 都有

此外，给定如下特化信息：对一切质数 $p$，

给定两个整数 $n$ 与 $k$。请你在区间 $[1,n]$ 内找出第 $k$ 小的满足 $f(x)=x$ 的正整数 $x$。若这样的数不足 $k$ 个，则输出 $-1$。

输入格式

第一行一个整数 $T$，表示有 $T$ 组测试数据。

接下来共 $T$ 行，一行两个整数 $n,k$。

输出格式

输出共 $T$ 行,一行一个整数，表示答案；若不存在则输出 $-1$。

3
10 5
3 3
11451419 19810

7
-1
222361

数据范围

对于 $10\%$ 的测试数据，$T = 1$。

对于另 $20\%$ 的测试数据，$1\le \sum n \le 10^6$。

对于 $100\%$ 的测试数据，$1\le T \le 10^5$，$1\le n\le 10^{12}$，$1\le k\le 10^{5}$。