Задача Nth. Розглянемо сукупність послідовностей:
послідовність №1 має вигляд 1, 2, 3, …, n, …;
послідовність №2 має вигляд 1, 4, 9, …, n2, …;
послідовність №3 має вигляд 1, 8, 27, …, n3, …;
і так далі;
послідовність №k має вигляд 1, 2k, 3k, …, nk, …;
і так далі.
Очевидно, що кожна з цих послідовностей монотонно зростає. Об’єднанням двох послідовностей будемо вважати послідовність, куди входять елементи обох послідовностей, теж у порядку зростання (числа, що належать обом послідовностям, належать об’єднанню лише один раз). Наприклад, об’єднання послідовностей №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 не задається явно, але гарантується, що значення кожної відповіді не перевищуватиме 1019. Програма повинна вивести на екран (пристрій стандартного виведення) відповідь для кожного з запитів (теж у один рядок, розділяючи пропусками).
Приклад
Введення
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.