{"raw_statement":[{"iden":"background","content":"![](https://cdn.luogu.com.cn/upload/image_hosting/iflu3244.png)\n\n图片来自于 Solara570 的 B 站视频 [轻易相信简单直观的结论究竟有多危险？](https://www.bilibili.com/video/BV1PW41177Vb)。\n\n很久以前的某一天，小 A 在 B 站上无意间刷到了这个视频。视频中的无穷幂塔方程及其「简单直观，但暗藏陷阱」的解法令他影响深刻。\n$$\n\\Huge x ^ {x ^ {x ^ {x ^ {x}}}}\n$$"},{"iden":"statement","content":"如果小 A 是一个，一个一个一个毒瘤，他会让你求解套了十层甚至九层的幂塔方程，但他不是。\n\n他想让你求解：\n$$\nx ^ x\\equiv D \\pmod n\n$$\n\n保证 $n$ 的最大质因子不超过 $10 ^ 5$，且 $D$ 与 $n$ 互质。\n\n你需要保证得到的解 $x$ 为 $[0, 2 ^ {125}]$ 范围内的整数。若该范围内无解，输出 $-1$；若存在多解，输出任意一个。\n\n多组测试数据。"},{"iden":"input","content":"第一行一个整数 $S$，表示该测试点的 Subtask 编号。\n\n第二行一个整数 $T$，表示数据组数。接下来 $T$ 组测试数据，每组数据形如：\n\n- 第一行两个整数 $n, D$。\n- 第二行若干递增的质数 $p_1, p_2, \\cdots, p_k$，表示 $n$ 的所有质因子。"},{"iden":"output","content":"输出 $T$ 行 $[-1, 2 ^ {125}]$ 范围内的整数。"},{"iden":"note","content":"**「数据范围与约定」**\n\n**本题采用捆绑测试**。\n\n- Subtask #1（5 points）：$n\\leq 20$。\n- Subtask #2（8 points）：$n\\leq 400$。依赖 Subtask #1。\n- Subtask #3（11 points）：$n$ 是质数，$T\\leq 10 ^ 4$。\n- Subtask #4（15 points）：$\\mu(n) \\neq 0$，$T\\leq 100$。\n- Subtask #5（9 points）：$\\mu(n) \\neq 0$，$T\\leq 10 ^ 4$。依赖 Subtask #4。\n- Subtask #6（13 points）：$n = p ^ k(p \\in \\mathrm{prime})$，$T\\leq 100$。\n- Subtask #7（7 points）：$n = p ^ k(p \\in \\mathrm{prime})$，$T\\leq 10 ^ 4$。依赖 Subtask #3，#6。\n- Subtask #8（6 points）：$n$ 的最大质因子不超过 $ 1064$。依赖 Subtask #2。\n- Subtask #9（16 points）：$n\\leq 10 ^ 9$，$T\\leq 10 ^ 4$。\n- Subtask #10（10 points）：无特殊限制。依赖 Subtask #5，#7，#8，#9。\n\n对于 $100\\%$ 的数据：\n\n- $1\\leq T\\leq 4\\times 10 ^ 4$。\n- $2\\leq n \\leq 10 ^ {18}$。\n- $1\\leq D < n$，$D\\perp n$。\n- $2\\leq p_1 < p_2 < \\cdots < p_k \\leq 10 ^ 5$。\n\n**「帮助与提示」**\n\n选手可以通过边读入边试除的方式判断何时停止读入 $n$ 的质因子。\n\n**「题目来源」**\n\n- [Sweet Round 8](https://www.luogu.com.cn/contest/73382) F\n- Idea & Solution：[demonlover923](https://www.luogu.com.cn/user/152997) & [codecode](https://www.luogu.com.cn/user/119526)。\n- Tester：[Alex_Wei](https://www.luogu.com.cn/user/123294)。\n\n**Update on 2025.5.30**：本题可以做 $p_k\\leq 10 ^ {18}$。"}],"translated_statement":null,"sample_group":[["0\n10\n7 4\n7\n16 3\n2\n6 1\n2 3\n144 5\n2 3\n2520 11\n2 3 5 7\n999999 2\n3 7 11 13 37\n22511 21795\n22511\n47067727606562827 30911969774113407\n3083 13697 25747 43291\n2147483648 2333333\n2\n675288511488360000 510472780110265817\n2 3 5 7 11","25\n11\n1\n101\n4811\n219871229\n16139671\n760913896873844308082367046696111\n1221598821\n24445987958110300438937\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}