==Include(page="template/taskheader" task_id="nodiv")==

Aenag Lurtseam a ajuns in cele din urma la facultate, unde a si primit prima tema. De data aceasta el se confrunta cu o noua problema: primeste un numar natural $N$ si i se cere sa il scrie ca suma de termeni de forma $2^a3^b$. Desi tema i s-a parut initial usoara, s-a lovit de o noua constrangere - suma nu trebuie sa contina doi termeni diferiti astfel incat unul sa il divida pe celalalt. De exemplu $15 = 2^13^1 + 2^03^2$ este o descompunere buna, dar $18 = 2^13^1 + 2^23^1$ nu.

Aenag Lurtseam a ajuns in cele din urma la facultate, unde a si primit prima tema. De data aceasta el se confrunta cu o noua problema: primeste un numar natural $N$ si i se cere sa il scrie ca suma de termeni de forma $2^a^3^b^$. Desi tema i s-a parut initial usoara, s-a lovit de o noua constrangere - suma nu trebuie sa contina doi termeni diferiti astfel incat unul sa il divida pe celalalt. De exemplu $15 = 2^1^3^1^ + 2^0^3^2^$ este o descompunere buna, dar $18 = 2^1^3^1^ + 2^2^3^1^$ nu.

h2. Cerinta

h2. Restrictii

* $1 ≤ N ≤ 2^63 - 1$

* $1 ≤ N ≤ 2^63^ - 1$

* $1 ≤ T ≤ 10 000$
h2. Exemple

| 2 1 1 0 2
  1 4 0
  2 3 0 0 2

| 15 = 2^13^1 + 2^03^2
  16 = 2^43^0
  17 = 2^33^0 + 2^03^2 |

| 15 = 2^1^3^1^ + 2^0^3^2^
  16 = 2^4^3^0^
  17 = 2^3^3^0^ + 2^0^3^2^ |

==Include(page="template/taskfooter" task_id="nodiv")==