Закодированные координаты

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

Каждое место определяется двумя координатами: 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" в отдельной строке.

Примеры