Задача Nth.   Розглянемо сукупність послідовностей:

послідовність №1 має вигляд 1, 2, 3, …, n, …;

послідовність №2 має вигляд 1, 4, 9, …, n², …;

послідовність №3 має вигляд 1, 8, 27, …, n³, …;

і так далі;

послідовність №k має вигляд 1, 2^k, 3^k, …, n^k, …;

і так далі.

Очевидно, що кожна з цих послідовностей монотонно зростає. Об’єднанням двох послідовностей будемо вважати послідовність, куди входять елементи обох послідовностей, теж у порядку зростання (числа, що належать обом послідовностям, належать об’єднанню лише один раз). Наприклад, об’єднання послідовностей №2 та №3 має вигляд: 1, 4, 8, 9, 16, 25, 27, 36, 49, 64, 81, 100, 121, 125, …

Технічні умови.  Напишіть програму Nth, яка оброблятиме серію запитів вигляду: знайти N-й елемент об’єднання послідовностей №a та №b.

Програма читає з клавіатури (пристрою стандартного введення) спочатку кількість запитів q (1≤ q ≤100), потім самі запити. Кожен запит має вигляд трійки чисел a b N, де aта b — номери послідовностей, N — номер шуканого елемента в об’єднанні послідовностей. Всі вхідні дані записані в один рядок і розділені пропусками (не обов’язково одинарними). Усі числа a b N цілі, не менші 1; верхнє обмеження на a b N не задається явно, але гарантується, що значення кожної відповіді не перевищуватиме 10¹⁹. Програма повинна вивести на екран (пристрій стандартного виведення) відповідь для кожного з запитів (теж у один рядок, розділяючи пропусками).

Приклад

Введення

3   2 3 4   3 2 11   4 7 17

Виведення

9 81 38416

Примітка. Не менш ніж у 30% тестів гарантовано, що кількість запитів q=1, номери послідовностей a та b в межах 1≤a<b≤9, номер шуканого елемента у межах1≤j≤100.