{"problem":{"name":"[CoE R4 B/Stoi2041] 龙拳","description":{"content":"对于 $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))$。 多次询问，每次询问给定正整数","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8302"},"statements":[{"statement_type":"Markdown","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$。\n\n## Input\n\n第一行一个正整数 $T$ 表示询问次数。\n\n接下来 $T$ 行，每行两个正整数 $n,k$，表示一次询问。\n\n## Output\n\n对于每组询问输出一个整数表示答案。\n\n[samples]\n\n## Background\n\n![](bilibili:BV1fx411N7bU?page=28)\n\n## Note\n\n### 样例解释\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$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8302","tags":["模拟","数学","数论","洛谷原创","O2优化","枚举","洛谷月赛"],"sample_group":[["2\n2 3\n3 4\n","0\n-1\n"]],"created_at":"2026-03-03 11:09:25"}}