题目描述

对于 $n \in \mathbb{Z_{\ge 2}}$，设 $g(n)$ 为 $n$ 的小于 $n$ 的最大约数，如 $g(7) = 1, g(12) = 6$。

定义 $f(n) = n + g(n)$。记 $f^{(0)}(n)=n$，且对 $m \in \mathbb{Z_{\ge 0}}$ 有 $f^{(m+1)}(n)=f(f^{(m)}(n))$。

多次询问，每次询问给定正整数 $n,k$，求最小的自然数 $m_0$，使得对于任意 $m \ge m_0$，均有 $f^{(m)}(n) \mid f^{(m+k)}(n)$。

若不存在这样的 $m_0$，则令 $m_0=-1$。

输入格式

第一行一个正整数 $T$ 表示询问次数。

接下来 $T$ 行，每行两个正整数 $n,k$，表示一次询问。

输出格式

对于每组询问输出一个整数表示答案。

2
2 3
3 4

0
-1

提示

样例解释

当 $n=2,k=3$ 时，$m_0=0$。

当 $n=3,k=4$ 时不存在满足条件的 $m_0$。

数据规模

本题采用捆绑测试。

• 子任务 $1$（$1$ 分）：$T=k=1$；
• 子任务 $2$（$12$ 分）：$T,n,k \le 10$；
• 子任务 $3$（$24$ 分）：$T \le 10,n \le 10^5$；
• 子任务 $4$（$36$ 分）：$T \le 10^3$；
• 子任务 $5$（$27$ 分）：无特殊限制。

对于 $100\%$ 的数据，保证 $1 \le T \le 2 \times 10^6$，$2 \le n \le 3 \times 10^7$，$1 \le k \le 10^9$。