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