POLSKI SPOJ

Liczba k-cyfrowych liczb

Ile jest k-cyfrowych liczb naturalnych w systemie o podstawie n?

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 10⁵) oznaczająca liczbę przypadków testowych. W kolejnych d wierszach podane są dwie liczby całkowite k, n (1 ≤ k ≤ 64, 2 ≤ n ≤ 16).
Dla danych wejściowych zachodzi dodatkowo warunek: n^k ≤ 2⁶⁴.

Wyjście
Dla każdego przypadku testowego w osobnym wierszu należy wypisać jedną liczbę całkowitą będącą odpowiedzią na postawione pytanie.

Przykład

Wejście
4
1 10
2 10
3 3
4 2

Wyjście
10
90
18
8