Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_14_15 - Kierowca rajdowy

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, 105]. W kolejnych t liniach znajdują się zestawy danych.

Każdy zestaw danych składa się z dwóch liczb całkowitych n ∈ [1, 109] i k ∈ [2, 109] 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.

Dodane przez:Maciej Boniecki
Data dodania:2021-12-17
Limit czasu wykonania programu:5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.