Вежа

Алан любить будувати вежі з будівельних цеглин. Його вежі складаються з прямокутних паралелепіпедів з квадратною основою, причому всі вони мають однакову висоту h = 1. Алан розміщує ці паралелепіпеди один на одному:

Рисунок 1: Вежа з трьох цеглин, коли Алан обирає a_2 = 2.

Нещодавно на уроці математики Алан дізнався про об'єм, і тепер він хоче обчислити об'єм своєї вежі. Довжини основ паралелепіпедів (зверху вниз) Алан визначає так:

1. Довжина a_1 першого квадрата дорівнює одиниці.

2. Потім Алан обирає довжину a_2 другого квадрата.

3. Далі Алан обчислює довжину a_n (n > 2) за формулою 2a_2a_{n-1} - a_{n-2}. Не питайте, чому він обрав таку формулу; просто скажімо, що він дуже своєрідний молодий хлопець.

Наприклад, якщо Алан обирає a_2 = 2, то a_3 = 8 - a_1 = 7; див. Рисунок 1. Якщо Алан обирає a_2 = 1, то a_n = 1 для всіх n N; див. Рисунок 2.

Тепер Алан цікавиться, чи може він обчислити об'єм вежі з N послідовних будівельних цеглин. Допоможіть Алану і напишіть програму, яка обчислює цей об'єм. Оскільки він може бути досить великим, достатньо обчислити відповідь за модулем заданого натурального числа m.

Вхідні дані

Вхід містить кілька тестових випадків. Перша строка містить число t (t ≤ 10^5), що позначає кількість тестових випадків. Потім слідують t тестових випадків. Кожен з них подається в окремій строкі, що містить три цілі числа a_2, N, m (1 ≤ a_2, m ≤ 10^9, 2 ≤ N ≤ 10^9), розділені одним пробілом, де a_2 позначає фіксовану довжину другого квадрата на кроці 2, а N позначає кількість цеглин, побудованих Аланом.

Вихідні дані

Для кожного тестового випадку (a_2, N, m) обчисліть об'єм вежі з N послідовних цеглин, побудованих Аланом відповідно до кроків (1-3), і виведіть його залишок за модулем m.

Рисунок 2: Вежа з чотирьох цеглин, коли Алан обирає a_2 = 1.

Приклади