The statement of this problem is very simple. Given two number n and k, you need to find the maximum power of k (i.e. x) such that n! % k^x = 0. Here n! is the notation of n factorial. If you are not familiar with the notation,

n! = 1 * 2 * 3 * 4 * 5 * 6 ... * n

Input

First line of the input will contain an integer t (1 ≤ t ≤ 20) denoting the number of test case. The next t lines contain two integer number n and k as described above.

Constraints

For easy version, 1 ≤ n ≤ 10, 2 ≤ k ≤ 10

For harder version, 1 ≤ n ≤ 100000000, 2 ≤ k ≤ 100000000

Output

For each test case, print “Case t: x” where t is the test case number and x is the maximum power of k for which n! % k^x = 0.

Example

Input:
2
5 2
1000 2
Output:
Case 1: 3
Case 2: 994

Explanation

In the first test case, n = 5 and k = 2. So, n! = 120.

• 120 % 2⁰ = 0
• 120 % 2¹ = 0
• 120 % 2² = 0
• 120 % 2³ = 0
• 120 % 2⁴ = 8
• 120 % 2⁵ = 24
• 120 % 2⁶ = 56
• 120 % 2⁷ = 120

So, the answer should be 3.

Problem Setter: Rakibul Islam