== include(page="template/taskheader" task_id="dtcsu") ==

Poveste şi cerinţă...

Se dau toate numerele de forma 2^a^3^b^5^c^7^d^ (a,b,c, d naturale) din intervalul [0, 10^18^] urmate de Q query-uri de forma: "se poate scrie N ca 2^w^3^x^5^y^7^z^ unde w, x, y, z naturale?" Numarul total de solutii reprezinta aproximativ 20% din numarul total de queryuri.

h2. Date de intrare

Fişierul de intrare $dtcsu.in$ ...

Fişierul de intrare $dtcsu.in$ contine pe primele 276997 toate numerele de forma mentionata anterior. Urmeaza pe o noua linie numarul natural Q reprezentand numarul de query-uri, iar pe fiecare dintre urmatoarele Q numere se gaseste cate o valoare N, pe care va trebui sa o verificati.

h2. Date de ieşire

În fişierul de ieşire $dtcsu.out$ ...

Fişierul de ieşire $dtcsu.out$ contine pe o singura linie numarul de valori ale lui N care satisfac cerinta.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ Q ≤ 5000000$
* $0 ≤ X ≤ 10^18^$

h2. Exemplu
table(example). |_. dtcsu.in |_. dtcsu.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| ...(276997 linii)
3
1
13
10
| 2

|
h3. Explicaţie

...

1 = 2^0^3^0^5^0^7^0^
10 = 2*5

== include(page="template/taskfooter" task_id="dtcsu") ==