Problem Statement

Rar the Cat is tired of cooking up stories to make a problem look interesting. Since this is a math problem, it wouldn't be interesting anyway.

While doing exponentiate, Rar always wondered how many digits A^B is, for the value of A and B which Rar the Cat will provide.

Both A and B will be strictly positive and will fit into a 64-bit signed integer (long long).

Input

There are multiple testcases for this problem, the first line of input will indicate the number of testcases, TC.

TC lines follow and each line will have A and B

Output

For each testcase, output the number of digits of A^B

Subtasks

Subtask 1 (13%): TC = 1, it is also guaranteed that A^B ≤ 2,000,000,000

Subtask 2 (28%): TC = 1, no other restrictions

Subtask 3 (59%): 0 ≤ TC ≤ 1000000

Sample Input 1

5
2 1
2 2
2 3
2 4
2 5

Sample Output 1

1
1
1
2
2

Explanation for Sample Output 1

The input is asking for the number of digits for the powers of 2. The first 5 powers of 2 are : 2, 4, 8, 16, 32 and thus they are of 1, 1, 1, 2, 2 digits respectively.

Sample Input 2

1
123456789 123456789

Sample Output 2

998952458