Гуннар - досить старий і забудькуватий дослідник. Зараз він пише статтю про безпеку в соціальних мережах, яка вміщує деякі елементи комбінаторики. Дослідник написав програму для знаходження біноміальних коефіцієнтів, щоб перевірити деякі розрахунки.
Біноміальний коефіцієнт Ck_n - це число
де n і k - невід`ємні числа.
Гуннар використовує свою программу для розрахунку Ck_n і отримує число m як результат. На жаль, як було сказано вище, він забудькуватий, тому й забув числа n і k, які він використав як вхідні дані. Ці два числа були результатом довгих розрахунків і були записані на одному з кільканадцяти листків, що лежали на його столі. Замість того, щоб пошукати в паперах, він вирішив відновити числа n і k за отриманою відповіддю. Чи можете Ви допомогти Гуннару знайти всі можливі такі значення?
Перший рядок має кількість тестів, не більших 100. Кожен тест задається в одному рядку й має ціле число m (2 ≤ m ≤ 10^15
) - результат програми Гуннара.
Для кожного теста вивести два рядка. Перший рядок повинен виводити кількість способів, за яких можна виразити m за допомогою біноміального коефіцієнта. У другому рядку повинні бути всі пари (n, k), які задовільняють Ck_n = m. Пари потрібно розкласти за збільшенням n, а у випадку рівності - за збільшенням k. Формат виводу пар наведений у прикладі.