POLSKI SPOJ

Cześć, mam na imię Janek i to ja wołałem pomocy. Jestem dobrym duchem tego zadania. Słuchaj, bo jest taka sprawa. Tak wyszło, że utknąłem w mrocznej pustce Wielkiego Sędziego i nie wiem jak się wydostać (autor zadania też jest bezradny). To ten … pomożesz mi? Aby mnie uwolnić musisz rozwiązać to zadanie, a w zamian przyniosę Ci szczęście w następnych zadaniach. Musiałbyś policzyć długość liczby w dowolnym systemie pozycyjnym. Sam zrobiłbym to zadanie w 5 minut, ale wiesz, mroczna pustka – nic tu nie ma, mojego komputera też nie. To jak, umowa stoi?

Wejście

Tak jak powiedział Janek zadanie to polega na obliczeniu długości liczby w dowolnym systemie pozycyjnym. W pierwszym wierszu wejścia znajduje się jedna liczba naturalna t (t<=10³) oznaczająca liczbę zestawów danych. Każdy zestaw składa się z dwóch liczb całkowitych nieujemnych: n, czyli dana liczba zapisana w systemie dziesiętnym (n<=10¹²) i p, czyli podstawa systemu, w którym należy podać długość liczby n (2<=p<=10³).

Wyjście

Dla każdego zestawu danych należy podać jedną liczbę, będącą długością liczby n zapisanej w systemie pozycyjnym p.

Przykład

Wejście:
2
7 2
0 7

Wyjście:
3
1