POLSKI SPOJ

Leszek jest kierowcą rajdowym. Jego samochód posiada skrzynię sekwencyjną o n biegach. Oznacza to, że bieg i możemy zmienić wyłącznie na bieg i - 1 albo i + 1. Na 1 biegu samochód jedzie z prędkością 1 km/h. Po zmianie biegu z i - 1 na i samochód zwiększa prędkość i-krotnie. Po zmianie biegu z i na i - 1 samochód zmniejsza prędkość i-krotnie. Samochód posiada również wyświetlacz pokazujący aktualną prędkość w k-tym systemie liczbowym.

Leszek od razu po ruszeniu zmienia biegi od 1 do n, aby uzyskać jak największą prędkość. Niestety nasz bohater potrafi czasami wpaść w panikę, gdy zobaczy na wyświetlaczu bardzo dużą liczbę. Żeby rozwiązać ten problem mechanicy z zespołu Leszka postanowili zakryć na wyświetlaczu wszystkie końcowe zera, które wyświetlają się podczas jazdy na n-tym biegu.

Odpowiedz na pytanie, ile zer zakryją mechanicy?

Wejście

W pierwszej linii wejścia znajduje się liczba zestawów danych t ∈ [1, 10⁵]. W kolejnych t liniach znajdują się zestawy danych.

Każdy zestaw danych składa się z dwóch liczb całkowitych n ∈ [1, 10⁹] i k ∈ [2, 10⁹] określających odpowiednio liczbę biegów w skrzyni sekwencyjnej oraz system liczbowy w jakim pokazywana jest aktualna prędkość.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać odpowiedź na pytanie, ile zer zakryją mechanicy.

Przykład

Wejście:

3
4 2
6 10
10 5

Wyjście:

3
1
2

Wyjaśnienie do przykładu:

• W 1 zestawie danych Leszek porusza się z prędkością 24 km/h, co odpowiada 11000 w dwójkowym systemie liczbowym.
• W 2 zestawie danych Leszek porusza się z prędkością 720 km/h.
• W 3 zestawie danych Leszek porusza się z prędkością 3628800 km/h, co odpowiada 1412110200 w piątkowym systemie liczbowym.