Fişierul intrare/ieşire:	jap.in, jap.out	Sursă	Algoritmiada 2009, Runda 2
Autor	Bogdan-Cristian Tataroiu	Adăugată de	Bogdan-Cristian Tataroiu •bogdan2412
Timp execuţie pe test	0.25 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Jap

J. Tamplaru' are de rezolvat urmatoarea problema pentru ora de mate:

Sa se determine numarul de elemente distincte generate de secventa a^b (a la puterea b), pentru a, b numere intregi cu 1 ≤ a ≤ N si 1 ≤ b ≤ M.

Tatal sau, G. Tamplaru' I, s-a uitat peste tema fiului sau si dupa ce a aflat de existenta informaticii cand isi construia biroul in problema trecuta, s-a hotarat sa va dea voua problema sa o rezolvati pentru diverse valori ale lui N si M.

Date de intrare

Fişierul de intrare jap.in contine pe prima linie numarul T de teste. Urmatoarele T linii contin pe fiecare linie cate 2 numere naturale N si M cu semnificatiile de mai sus.

Date de ieşire

Fişierul de ieşire jap.out va contine T linii, cate una pentru fiecare test din intrare.

Restricţii

• 1 ≤ T ≤ 10 000
• 1 ≤ N, M ≤ 100 000
• 20% din testele folosite la evaluare vor avea T = 1 si 1 ≤ N, M ≤ 1 000
• 70% din testele folosite la evaluare vor avea T ≤ 100
• Important Numarul de valori diferite ale lui M din fisierul de intrare nu va fi mai mare de 30

Exemplu

Explicatie

Pentru exemplul al doilea secventa generata este formata din elementele 1¹ = 1, 1² = 1, 2¹ = 2, 2² = 4. Numarul de elemente distincte din aceasta secventa este 3.

Cum se trimit solutii?