jap

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

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':problema/scandura, s-a hotarat sa va dea voua problema sa o rezolvati pentru diverse valori ai lui $N$ si $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':problema/scandura, s-a hotarat sa va dea voua problema sa o rezolvati pentru diverse valori ale lui $N$ si $M$.

h2. Date de intrare

h2. 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 ≤ 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$

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

| 1

| 2

5 5

| 15

2 2
| 19
3

|

h3. Explicatie
 
Pentru exemplul al doilea secventa generata este formata din elementele $1^1^ = 1, 1^2^ = 1, 2^1^ = 2, 2^2^ = 4$. Numarul de elemente distincte din aceasta secventa este $3$.
 

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

3564