Realm of Numericon

In the mysterious Realm of Numericon, a group of ancient mathematicians discovered a unique pattern related to prime numbers. They found that to uncover the deepest secrets of Numericon, one must determine the largest $x$ such that $m^x$ divides $^nC_r$ where $n, r$ and $m$ are integral parts of the mystery.

$^nC_r =\frac{n!}{(n - r)!\space\cdot\space r!}$​

As the chosen one to unlock Numericon's secrets, you are tasked with creating a program to calculate the maximum value of $x$ for given $n, r$ and $m.$ Can you unveil the hidden wisdom of Numericon and become the savior of this mystical land?

Input

The first line of the input contains an integer $T$ indicating the number of tests to be conducted.

Each of the following $T$ lines consists of three integers $n, r,$ and $m$ separated by a space.

Constraints

• $1 ≤ T ≤ 10^3$

• $1 ≤ n ≤ 10^{18}$

• $0 ≤ r ≤ n$

• $2 ≤ m ≤ 10^{12}$

Output

You have to output $T$ lines in format “Case $c$: $x$”(without quotes) where $c$ is the test case number and $x$ is the result of the test case. Check out the samples for more clarification.

Sample

Input	Output
5 8 3 2 10 5 3 5 4 4 9 5 7 16 8 3	Case 1: 3 Case 2: 2 Case 3: 0 Case 4: 1 Case 5: 2
Explanation Test $1:$ For $n = 8, r = 3$ and $m = 2,$ we have $^8C_3 = 56.$ Here largest $2^3 = 8$ that divides $56,$ so $x$ is $3.$ Test $2:$ For $n = 10, r = 5$ and $m = 3,$ we have $^{10}C_5 = 252.$ Here largest $3^2 = 9$ that divides $252,$ so $x$ is $2.$ Test $3:$ For $n = 5, r = 4$ and $m = 4,$ we have $^5C_4 = 5.$ Here largest $4^0 = 1$ that divides $5,$ so $x$ is $0.$

Be careful about the output formatting and newline (‘\n’) at the end.