PROGRAMMING:Base system

Convert a decimal number to $$k $$system, and find out how many $$0 $$$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$$
For example, the decimal $$(738)_{ 10}$$
After conversion to 11, it is $$(1010)_{ 9} So he has two zeros
###Input format:
The first line gives the number of sample groups $$t (1 < = T < = 100000)$$
The next $$t $$line, each line gives two positive integers $$n, K (1 < = n < = 10 ^ {9}, 1 < K < 10)$$
###Output format:
For each group of inputs, output the number of $$0 $$converted to $$k $$in one line.
###Input example:
Here is a set of inputs. For example:
```in
seven
79 8
8 6
91 4
48 2
52 8
37 6
70 2
```
###Output example:
The corresponding output is given here. For example:
```out
0
0
0
four
0
one
four
```







answer：If there is no answer, please comment