{"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\"\u003eAs a newbie, XianYu is now learning generating function!\u003cbr\u003eGiven a series $\\{a\\}\u003d(a_0,a_1,a_2,\\cdots)$, we can easily define its exponential generating function as $g_{\\{a\\}}(x) \u003d \\sum\\limits_{i\u003d0}^{\\infty}\\dfrac{a_i}{i!}x^i$.\u003cbr\u003eNow we define a series $\\{u_c\\}\u003d(c^0,c^1,c^2,\\cdots)$ and let $e_c$ represents the ${u_c}$ with $0$ filled in all its even items. Formally, ${\\{e_c\\}}\u003d(0,c^1,0,c^3,0,c^5,\\cdots)$.\u003cbr\u003e\u003cbr\u003e\u0027Do you know convolution?\u0027\u003cbr\u003e\u0027GU GU.\u0027 GuGu utters.\u003cbr\u003e\u0027Well, let me show you.\u003cbr\u003eGiven two generating function $g_{\\{a\\}}$ and $g_{\\{b\\}}$, the convolution can be represented as $G(x)\u003d(g_{\\{a\\}}*g_{\\{b\\}})(x)\u003d\\sum\\limits_{n\u003d0}^{\\infty}(\\sum\\limits_{i+j\u003dn}a_ib_j)x^n$.\u003cbr\u003eIt is quite easy, right?\u0027\u003cbr\u003e\u0027GU GU.\u0027 GuGu utters.\u003cbr\u003e\u0027Ok. Now you have to find the coefficient of $x^n$ of the convolution $G(x)\u003d(g_{\\{u_A\\}}*g_{\\{e_\\sqrt{B}\\}})$, given $n$, $A$ and $B$.\u003cbr\u003eLet $G_n$ representes that coefficient, you should tell me $n!G_n$.\u003cbr\u003eYou may know the severity of unsolving this problem.\u0027\u003cbr\u003e\u003cbr\u003eAs GuGu is not that kind of good for it, it turns to you for help.\u003cbr\u003e\u0027GU GU!\u0027 GuGu thanks.\u003cbr\u003e\u003cbr\u003e\u003cdiv style\u003d\"font-family:Times New Roman;font-size:14px;background-color:F4FBFF;border:#B7CBFF 1px dashed;padding:6px\"\u003e\u003cdiv style\u003d\"font-family:Arial;font-weight:bold;color:#7CA9ED;border-bottom:#B7CBFF 1px dashed\"\u003e\u003ci\u003eHint\u003c/i\u003e\u003c/div\u003e\u003cbr\u003eFirst Sample: $1!(\\dfrac{1^0}{0!}\\dfrac{\\sqrt{1}^1}{1!} + \\dfrac{1^1}{1!}\\dfrac{0}{0!}) \u003d 1 \\sqrt{1}$\u003cbr\u003eSecond Sample: $2!(\\dfrac{523^0}{0!}\\dfrac{0}{2!} + \\dfrac{523^1}{1!}\\dfrac{\\sqrt{12}^1}{1!} + \\dfrac{523^2}{2!}\\dfrac{0}{0!}) \u003d 2092 \\sqrt{3}$\u003cbr\u003eP.S.: $1046\\sqrt{12}$ is equal to the answer. However, $12$ has a factor $4\u003d2^2$ so it can\u0027t be output directly.\u003cbr\u003e\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"There is an integer $T$ in the first line, representing the number of cases.\u003cbr\u003eThen followed $T$ lines, and each line contains four integers $A,B,n,p$. The meaning of $A,B,n$ is described above, and that of $p$ will be described in Output session.\u003cbr\u003e$1\\leq T \\leq 10^5$\u003cbr\u003e$1\\leq A,B \\leq 10^6$\u003cbr\u003e$1\\leq n \\leq 10^{18}$\u003cbr\u003e$1\\leq p \\leq 10^{9}$"}},{"title":"Output","value":{"format":"HTML","content":"Let $\\sum\\limits_{i\u003d1}^{q} a_i\\sqrt{b_i}$ represents the answer, with $b_i \\neq b_j, \\gcd(b_i,b_j)\u003d1, 1\\leq i\u0026lt; j\\leq q$, and none of $b_i$\u0027s factors is square number.\u003cbr\u003ePrint $T$ lines only. Each line comes with a number $q$ and followed $q$ pairs of integers $a_i$ $b_i$, with $b_i$ in increasing order. Since $a_i$ may be large, please print $a_i\\%p$ instead. All integers in the same line should be seperated by exactly one space.\u003cbr\u003eYou may find that each answer is unique.\u003cbr\u003e"}},{"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\n1 1 1 7\r\n523 12 2 2100\r\n1 1 1000000000000000000 998244353\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 1 1\r\n1 2092 3\r\n1 121099884 1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}