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 2 ≤ a ≤ N si 2 ≤ 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 ai 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 ≤ 100
• Important Numarul de valori diferite ale lui M din fisierul de intrare nu va fi mai mare de 10
• 1 ≤ N, M ≤ 100 000

Exemplu

Cum se trimit solutii?