Кодовані координати

Ви стежите за терористичною групою, яка планує великий напад десь поблизу. Терористи обмінюються закодованими координатами, і ви підозрюєте, що напад відбудеться в одному з місць, описаних цими координатами. Ви перехопили відповідні комунікації для ряду місць, які хочете дослідити.

Кожне місце визначається координатами x та y, кожна з яких є невід'ємним цілим числом, меншим за певне просте число P. Обидві координати закодовані окремо, використовуючи однаковий процес. Джерело надало вам інформацію про процес декодування однієї координати. Вхід цього процесу складається з п'яти значень: A, B, C, K та N.

Центральним у процесі декодування є набір з трьох функцій, визначених одна через одну та вхідне значення K:

F(n + 1) = G(n) + H(n)

G(n + 1) = K*F(n) + H(n- 1)

H(n + 1) = F(n) + K*G(n)

Значення A, B та C використовуються для ініціалізації цих функцій наступним чином:

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

Декодована координата - це значення F(N) mod P.

Як ви могли помітити, є деяка важлива інформація, якої бракує: вам потрібне значення H(0) для обчислення G(2). Хоча у вас немає цього значення, ви знаєте, що координати x та y використовують одне й те саме значення для H(0). На щастя, ви вже отримали координати x для місць. Ваші колеги припустили, що цього недостатньо для обчислення координат y, але ви хочете довести, що вони помиляються.

Вхідні дані

На першому рядку одне додатне число: кількість тестових випадків, не більше 100. Після цього для кожного тестового випадку:

• один рядок з простим числом P (2 ≤ P ≤ 19997).

• один рядок з п'ятьма цілими числами, розділеними пробілами: A[x], B[x], C[x], K[x] та N[x] (0 ≤ A[x], B[x], C[x], K[x] < P та 1 ≤ N[x] ≤ 10^9): параметри для координати x.

• один рядок з п'ятьма цілими числами, розділеними пробілами: A[y], B[y], C[y], K[y] та N[y] (0 ≤ A[y], B[y], C[y], K[y] < P та 1 ≤ N[y] ≤ 10^9): параметри для координати y.

• один рядок з одним цілим числом x (0 ≤ x < P): координата x.

Вихідні дані

Для кожного тестового випадку:

• один рядок з одним цілим числом: обчислена координата y. Якщо ваші колеги мають рацію, і немає точно однієї дійсної координати y, виведіть "UNKNOWN" в одному рядку.

Приклади