Leonhard Euler (1707-1783) wielkim matematykiem był. W tym zadaniu rozważymy jedną z funkcji nazwanych na jego cześć, a mianowicie funkcję $\varphi$ Eulera.

Wartością funkcji $\varphi$ dla liczby naturalnej $ n $ jest liczba liczb $ k $ ($1 \le k \le n $) względnie pierwszych z $ n $. Dwie liczby są względnie pierwsze, jeśli nie mają wspólnego dzielnika większego niż 1. Na przykład $\varphi(6) = 2$, gdyż liczby 1 oraz 5 są względnie pierwsze z liczbą 6, natomiast liczby 2, 3, 4 i 6 nie są.

Zadanie, które mógłby zadać Euler, gdyby nadal żył, mogłoby być następujące: dla ustalonej liczby naturalnej $ n $ znajdź wszystkie liczby naturalne $ x $, które spełniają równanie $\varphi(x) = n$.

Input Format

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna $ t $ ($1 \le t \le 5$) określająca liczbę zestawów danych. W kolejnych $ t $ wierszach znajdują się opisy kolejnych zestawów danych. Każdy opis zawiera jedną liczbę naturalną $ n $ ($1 \le n \le 10^{10}$).

Output Format

Twój program powinien wypisać na wyjście odpowiedzi dla poszczególnych zestawów danych w kolejności ich występowania na wejściu. Odpowiedź dla zestawu składa się z dwóch wierszy. W pierwszym wierszu powinna się znaleźć liczba rozwiązań. W drugim wierszu powinny się znaleźć wszystkie rozwiązania równania podane w kolejności rosnącej. Jeśli równanie nie ma rozwiązań, to drugi wiersz odpowiedzi dla zestawu danych powinien pozostać pusty.

Example

Input

4
8
10
13
6

Output

5
15 16 20 24 30
2
11 22
0

4
7 9 14 18