Гуннар - досить старий і забудькуватий дослідник. Зараз він пише статтю про безпеку в соціальних мережах, яка вміщує деякі елементи комбінаторики. Дослідник написав програму для знаходження біноміальних коефіцієнтів, щоб перевірити деякі розрахунки.

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

де n і k - невід`ємні числа.

Гуннар використовує свою программу для розрахунку Ck_n і отримує число m як результат. На жаль, як було сказано вище, він забудькуватий, тому й забув числа n і k, які він використав як вхідні дані. Ці два числа були результатом довгих розрахунків і були записані на одному з кільканадцяти листків, що лежали на його столі. Замість того, щоб пошукати в паперах, він вирішив відновити числа n і k за отриманою відповіддю. Чи можете Ви допомогти Гуннару знайти всі можливі такі значення?

Вхідні дані

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

Вихідні дані

Для кожного теста вивести два рядка. Перший рядок повинен виводити кількість способів, за яких можна виразити m за допомогою біноміального коефіцієнта. У другому рядку повинні бути всі пари (n, k), які задовільняють Ck_n = m. Пари потрібно розкласти за збільшенням n, а у випадку рівності - за збільшенням k. Формат виводу пар наведений у прикладі.