{"raw_statement":[{"iden":"background","content":"![](bilibili:BV1fx411N7bU?page=28)"},{"iden":"statement","content":"对于 $n \\in \\mathbb{Z_{\\ge 2}}$，设 $g(n)$ 为 $n$ 的小于 $n$ 的最大约数，如 $g(7) = 1, g(12) = 6$。\n\n定义 $f(n) = n + g(n)$。记 $f^{(0)}(n)=n$，且对 $m \\in \\mathbb{Z_{\\ge 0}}$ 有 $f^{(m+1)}(n)=f(f^{(m)}(n))$。\n\n多次询问，每次询问给定正整数 $n,k$，求最小的自然数 $m_0$，使得对于任意 $m \\ge m_0$，均有 $f^{(m)}(n) \\mid f^{(m+k)}(n)$。\n\n若不存在这样的 $m_0$，则令 $m_0=-1$。"},{"iden":"input","content":"第一行一个正整数 $T$ 表示询问次数。\n\n接下来 $T$ 行，每行两个正整数 $n,k$，表示一次询问。"},{"iden":"output","content":"对于每组询问输出一个整数表示答案。"},{"iden":"note","content":"### 样例解释\n\n当 $n=2,k=3$ 时，$m_0=0$。\n\n当 $n=3,k=4$ 时不存在满足条件的 $m_0$。\n\n---\n\n### 数据规模\n\n**本题采用捆绑测试。**\n\n- 子任务 $1$（$1$ 分）：$T=k=1$；\n- 子任务 $2$（$12$ 分）：$T,n,k \\le 10$；\n- 子任务 $3$（$24$ 分）：$T \\le 10,n \\le 10^5$；\n- 子任务 $4$（$36$ 分）：$T \\le 10^3$；\n- 子任务 $5$（$27$ 分）：无特殊限制。\n\n对于 $100\\%$ 的数据，保证 $1 \\le T \\le 2 \\times 10^6$，$2 \\le n \\le 3 \\times 10^7$，$1 \\le k \\le 10^9$。\n"}],"translated_statement":null,"sample_group":[["2\n2 3\n3 4\n","0\n-1\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}