{"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\"\u003eNoticeļ¼Don\u0027t output extra spaces at the end of one line.\u003cbr\u003e\u003cbr\u003eDodo and ddd rent a house together. The house has several bedrooms of different sizes. They all want to get the biggest one, so they come up with a strategy to allocate the biggest room. The strategy is as follows:\u003cbr\u003e\u003cbr\u003e- Each of them chooses an integer in $[0,t]$ randomly, where $t$ is a constant value. Call the number chosen by them $v_1$ and $v_2$ respectively.\u003cbr\u003e\u003cbr\u003e- Generate an array $\\{X_n\\}$: define $X_0\u003dv_1+v_2$, for $n \\geq 0$, define $X_{n+1}\u003d(aX_n+c) \\mod m$, where $a, c, m$ are constant values.\u003cbr\u003e\u003cbr\u003e- If $X_{|v_1-v_2|}$ is an odd number, Dodo gets the biggest room. Otherwise, ddd gets it.\u003cbr\u003e\u003cbr\u003eddd wants to know the probability of him getting the biggest room. Please help him to calculate it. Please output the probability by using an irreducible fraction.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer $T(1 \\leq T \\leq 100)$, indicating the number of test cases.\u003cbr\u003e\u003cbr\u003eEach test case contains one line, which contains $4$ integers $t, a, c, m(2 \\leq m \\leq 10^6, 0 \\leq a, c \u0026lt; m, 0 \\leq t \u0026lt; \\frac{m}{2})$.\u003cbr\u003e\u003cbr\u003eIt is guaranteed that there are at most $12$ test cases with $m \u0026gt; 5000$.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"$T$ lines, each line contains an irreducible fraction, indicating the answer. "}},{"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\u003e5\r\n7 1 0 29\r\n7 0 1 29\r\n77 77 77 777\r\n84 74 26 363\r\n10 15 76 9479\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1/2\r\n1/8\r\n84/169\r\n3729/7225\r\n71/121\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}