Гуннар - достаточно старый и забывчивый исследователь. Сейчас он пишет статью о безопасности в социальных сетях, которая включает в себя некоторые элементы комбинаторики. Он написал программу для вычисления биномиальных коэффициентов, чтобы проверить некоторые расчеты.

Биномиальный коэффициент Ck_n - это число

где n и k - неотрицательные числа.

Гуннар использует свою программу для вычисления Ck_n и получил число m в качестве результата. К несчастью, поскольку он забывчивый, он забыл числа n и k, которые он использовал в качестве входных данных. Эти два числа были результатом долгих вычислений, и они были записаны на одном из многочисленных листков, лежащих на его столе. Вместо того чтобы поискать в бумагах, он решил восстановить числа n и k по полученному ответу. Можете ли Вы помочь ему найти все такие возможные значения?

Входные данные

Первая строка содержит количество тестов, не большее 100. Каждый тест задается в одной строке и содержит целое число m (2 ≤ m ≤ 1015) - результат программы Гуннара.

Выходные данные

Для каждого теста вывести две строки. Первая строка должна содержать количество способов выразить m при помощи биномиального коэффициента. Во второй строке должны располагаться все пары (n, k), удовлетворяющие Ck_n = m. Пары следует расположить по возрастанию n, а в случае равенства по возрастанию k. Формат вывода пар приведен в примере.