{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eThis class is on graph theory. Mr. Kruskal teaches babies the concept of minimal spanning tree, and how to calculate the minimal spanning tree of a given graph.\u003cbr\u003e\u003cbr\u003eNow, it\u0027s time for an in-class quizz. Mr. Kruskal shows a special graph $G$: $G$ is a complete undirected graph with $n$ vertices, and vertices in $G$ are indexed from $1$ to $n$. The weight of the edge between the $i$th vertex and the $j$th vertex is equal to $lcm(i+1,j+1)$. Babies are asked to find the minimal spanning tree of $G$.\u003cbr\u003e\u003cbr\u003eAs a super baby, Baby Volcano quickly finds an answer, but he is not sure on the correctness of his answer. Your task is to tell Baby Volcano the weight sum of all edges on the minimal spanning tree, so that he could verify his answer.\u003cbr\u003e\u003cbr\u003eGiven two positive integers, $lcm(i,j)$ is defined as the minimal positive integer $k$ satisfying both $i$ and $j$ are factors of $k$.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains a single integer $t (1 \\leq t \\leq 50)$, the number of testcases.\u003cbr\u003e\u003cbr\u003eFor each testcase, the first line contains two integers $n, K (1 \\leq n \\leq 10^{10}, 10^8 \\leq K \\leq 10^9)$.\u003cbr\u003e\u003cbr\u003eThe input guarantees that $K$ is a prime number.\u003cbr\u003e\u003cbr\u003eThe input guarantees that there are no more than $5$ testcases with $n \u0026gt; 10^9$."}},{"title":"Output","value":{"format":"HTML","content":"For each testcase, output a single line with a single integer, the answer module $K$."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n3 998244353\r\n100 998244353\r\n1000000000 998244353\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\r\n6307\r\n192026508\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}