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

Se defineste o progresie geometrica K ca fiind un sir strict crescator a de lungime K cu proprietatea ca exista o ratie q in (Q intersectat cu (1,2])) astfel incat ai sa fie egal cu ai-1*q pentru orice 2<=i<=K

O progresie geometrică de lungime <tex>k</tex> cu raţia <tex>r </tex> este un şir de numere naturale <tex>p(1),\ p(2),\  ... ,\ p(k)</tex> pentru care se respectă relaţia : <tex>p(i)\ =\ p(i-1)\ *\ r,\ 2 \le i \le k \hspace{0.1cm} , \hspace{0.1cm} r\hspace{0.1cm}\in\hspace{0.1cm}\mathbb{Q} \bigcap (1,2)</tex>.

Se asigura ca se poate demonstra ca numarul de progresii geometrice K care incep cu valoarea N este egal cu cel mai mare numarul natural X cu proprietatea ca X^K este divizor al lui N.

Se asigură că se poate demonstra că numărul de progresii geometrice de lungime <tex>k</tex> care au prima valoare egală cu <tex>N</tex> este egal cu cel mai mare număr natural <tex>X - 1</tex> cu proprietatea că <tex>X^{k - 1}</tex> este divizor al lui <tex>N</tex>.

Se defineste o progresie cuantica K ca fiind un sir strict crescator a de lungime K cu proprietatea ca exista o ratie q in (Q intersectat cu (1,2]) astfel incat ai sa fie egal cu ai-1^q pentru orice 2<=i<=K.

O progresie cuantică de lungime <tex>k</tex> cu raţia <tex>q</tex> este un şir de numere naturale <tex>p(1),\ p(2),\  ... ,\ p(k)</tex> pentru care se respectă relaţia : <tex>p(i)\ =\ p(i-1)\ ^{q},\ 2 \le i \le k \hspace{0.1cm} , \hspace{0.1cm} q \hspace{0.1cm}\in\hspace{0.1cm}\mathbb{Q} \bigcap (1,2)</tex>.

-Cate progresii cuantice au prima valoare intre 1 si N?  N=1e9

Câte progresii cuantice distincte de lungime <tex>k</tex> au prima valoare între <tex>2</tex> şi <tex>N</tex>?

h2. Date de intrare

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

Pe prima linie a fişierului de intrare se va afla numărul <tex>t</tex> de întrebări.
Pe următoarele <tex>t</tex> linii se vor afla câte 2 valori: <tex>n</tex> şi <tex>k</tex> cu semnificaţiile din enunţ.

h2. Date de ieşire

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

În fişierul de ieşire se vor regăsi <tex>t</tex> valori pe <tex>t</tex> linii diferite.
Pe linia numărul <tex>i</tex> se va regăsi răspunsul la a <tex>i</tex>-a întrebare.

h2. Restricţii

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

* <tex> t \le 10 </tex>
* <tex>k</tex> &le; <tex>10</tex>
* Subtask-ul <tex>1</tex> de <tex>20</tex> de puncte: <tex>n \le 10^{2}</tex>
* Subtask-ul <tex>2</tex> de <tex>40</tex> de puncte: <tex>n \le 10^{6}</tex>
* Subtask-ul <tex>3</tex> de <tex>40</tex> de puncte: <tex>n \le 10^{12}</tex>

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

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

| 3
30 2
149808 3
4230675774 3
| 10
24
282
|

h3. Explicaţie

...

Primele 10 progresii cuantice de lungime 2 sunt:
4 8
8 16
8 32
9 27
16 32
16 64
16 128
25 125
27 81
27 243

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