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 $v_1$ and $v_2$ respectively.
- Generate an array $\{X_n\}$: define $X_0=v_1+v_2$, for $n \geq 0$, define $X_{n+1}=(aX_n+c) \mod m$, where $a, c, m$ are constant values.
- If $X_{|v_1-v_2|}$ 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.
Input
The first line contains an integer $T(1 \leq T \leq 100)$, indicating the number of test cases.
Each test case contains one line, which contains $4$ integers $t, a, c, m(2 \leq m \leq 10^6, 0 \leq a, c < m, 0 \leq t < \frac{m}{2})$.
It is guaranteed that there are at most $12$ test cases with $m > 5000$.
Output
$T$ lines, each line contains an irreducible fraction, indicating the answer.