Migrated from Lutece 2878 Easy Math

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Yukikaze is learning number theory.

Yukikaze have $Q$ questions about primes. Each of them is like:

Given $5$ integers $p, a, b, w, k$, find the number of roots $(x,y)$ of the equation

If the answer is greater than $0$, output any one of them.

Input

The first line contains an integer $Q\ (1 \leq Q \leq 10)$.

Each of the next $Q$ lines contains $5$ integers $p, a, b, w, k\ (2 \leq p \leq 10^9, 0 \leq a, b, w < p, 1 \leq k < p^2 - 1)$, $p$ is a prime, and $w$ is not a quadratic residue modulo $p$. That is, no integer $i$ satisfies $i^2 \equiv w \pmod p$.

Output

For each of the $Q$ lines, if the root exists, output $\text{cnt}\ x\ y$ in a single line. Here $x$ and $y$ are an arbitrary root of the corresponding equation, and $\text{cnt}$ is the number of such roots. Otherwise, output $0$ in a single line.

Samples

7
5 3 2 2 2
5 0 4 2 3
5 4 0 3 12
5 4 3 2 2
5 4 0 2 13
19260817 6854583 1145415 30095 114514
998244353 994180708 696075960 7729 12784162037563392

2 1 1
3 3 1
12 2 2
0
1 4 0
2 5472139 619723
672850633555968 292438259 192012292

Note

For the first question of the example, the equation is

The roots are $x=1,y=1$ and $x=4,y=4$.

For the second question of the example, the equation is

The roots are $x=0,y=3$, $x=2,y=1$ and $x=3,y=1$.

You may use __int128 instead of long long to compute products and modulus of large integers when using GCC as the compiler.

Resources

The 20th UESTC Programming Contest Preliminary