## NAJCC - Can you do it

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 100Output:2

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

Added by: | Najmuzzaman |

Date: | 2015-03-13 |

Time limit: | 1s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM64 JS-MONKEY |