Notice：Don't output extra spaces at the end of one line.
Dodo 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:
- Each of them chooses an integer in [0,t] randomly, where t is a constant value. Call the number chosen by them v1 and v2 respectively.
- Generate an array {Xn}: define X0=v1+v2, for n≥0, define Xn+1=(aXn+c)modm, where a,c,m are constant values.
- If X|v1−v2| is an odd number, Dodo gets the biggest room. Otherwise, ddd gets it.
ddd 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.
输入格式
The first line contains an integer T(1≤T≤100), indicating the number of test cases.
Each test case contains one line, which contains 4 integers t,a,c,m(2≤m≤106,0≤a,c<m,0≤t<m2).
It is guaranteed that there are at most 12 test cases with m>5000.
输出格式
T lines, each line contains an irreducible fraction, indicating the answer.