Little Joey recently started his math lesson. Today he learnt about Logarithm. He is fascinated about the idea of logarithm and he thinks that he really understands the logic behind it. So he takes his calculator and tries to find some value using log. It is easy and fun. But the problem is he can’t find logarithm of a big number, because his calculator can calculate only 10 digits. So, he asks for your help. Of course, he knows that you are a good programmer and may be you will go to Google one day. He will give you two numbers k and N and you have to find the value of log_k(N).

Easy, isn’t it?

He knows that you are busy too, so he makes the problem easier by saying that, “you can assume that N will always be some power of k.”

Input

The first line of the input contains an integer T (T ≤ 1000), denoting the number of test cases. Each test case contains two numbers, k and N, where 1 < k ≤ 10 and 1 ≤ N ≤ 10^100.

Output

For each case, print the value of log_k(N).

Example

Input:
1
10 100

Output:
2

Contest arranged by প্রোগ্রামিং প্রবলেম (Programming Problem in Bengali)