Задача 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.