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

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  ,  r \hspace{0.1cm}\epsilon\hspace{0.1cm}\mathbb{Q} \bigcap (1,2)</tex>.

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 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</tex> cu proprietatea că <tex>X^k</tex> este divizor al lui <tex>N</tex>.

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>.

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  ,  q \hspace{0.1cm}\epsilon\hspace{0.1cm}\mathbb{Q} \bigcap (1,2)</tex>.

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>.

Câte progresii cuantice de lungime <tex>k</tex> au prima valoare între <tex>2</tex> si <tex>n</tex>?

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

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

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

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>

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 sunt:

Primele 10 progresii cuantice de lungime 2 sunt:

4 8
8 16
8 32