{"raw_statement":[{"iden":"background","content":"题目来自 BZOJ 2017 年 4 月月赛。"},{"iden":"statement","content":"令 $(1+\\sqrt{2})^n=e(n)+\\sqrt{2}f(n)$，其中 $e(n),f(n)$ 都是整数，显然有 $(1-\\sqrt{2})^n=e(n)-\\sqrt{2}f(n)$。令 $g(n)=\\operatorname{lcm}(f(1),f(2),\\dots,f(n))$。\n\n给定两个正整数 $n,p$，其中 $p$ 是质数，并且保证 $f(1),f(2),\\dots,f(n)$ 在模 $p$ 意义下均不为 $0$，请计算 $\\sum \\limits_{i=1}^n i\\times g(i)$ 模 $p$ 的值。"},{"iden":"input","content":"第一行包含一个正整数 $T$，表示有 $T$ 组数据。\n\n接下来是测试数据。每组测试数据只占一行，包含两个正整数 $n$ 和 $p$。"},{"iden":"output","content":"对于每组测试数据，输出一行一个非负整数，表示这组数据的答案。"},{"iden":"note","content":"对于 $100\\%$ 的数据，$1\\leq T\\leq 210$，$1\\leq n\\leq 10^6$，$2\\leq p\\leq 10^9+7$，$\\sum n\\leq 3\\times 10^6$。"}],"translated_statement":null,"sample_group":[["5\n1 233\n2 233\n3 233\n4 233\n5 233","1\n5\n35\n42\n121"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}