Encoded Coordinates

Sangkeun was tapping a terrorist's phone when he learned that a large attack had been announced. The terrorists send encoded coordinates to each other, and the attack will happen at one of them. Sangkeun managed to intercept a coordinate.

A coordinate splits into an x value and a y value, and both are non-negative integers smaller than a prime $P$. The x value and the y value are encoded separately, by the same procedure.

Encoding one value needs $A$, $B$, $C$, $K$, $N$. The procedure is written with three functions.

• $F(n+1) = G(n) + H(n)$
• $G(n+1) = K \times F(n) + H(n-1)$
• $H(n+1) = F(n) + K \times G(n)$

$A$, $B$, $C$ are the initial values of the functions.

• $F(1) = A$
• $G(1) = B$
• $H(1) = C$

The value becomes $F(N) \bmod P$.

One very important piece of information is missing from the procedure above. Computing $G(2)$ needs $H(0)$, and nothing reveals $H(0)$. All that is known about it is that the same $H(0)$ is used when computing x and when computing y. $H(0)$ is also a non-negative integer smaller than $P$.

Sangkeun happened to get the x value without decoding it. Write a program that recovers $H(0)$ from x and then computes y.

The first line contains the number of test cases, which is at most 100.

Each test case takes four lines. The first line contains a prime $P$ ($2 \le P \le 19997$). The second line contains $A_x$, $B_x$, $C_x$, $K_x$, $N_x$, the values used to encode the x value ($0 \le A_x, B_x, C_x, K_x < P$, $1 \le N_x \le 10^9$). The third line contains $A_y$, $B_y$, $C_y$, $K_y$, $N_y$, the values used to encode the y value ($0 \le A_y, B_y, C_y, K_y < P$, $1 \le N_y \le 10^9$). The fourth line contains the intercepted x value ($0 \le x < P$).

The intercepted x value really came out of the encoding, so at least one $H(0)$ produces it.

For each test case, print the y value on its own line. If several $H(0)$ produce the given x value and they do not all lead to the same y value, print UNKNOWN instead of the y value.