Sajeeb and Shoikot are two friends. Both are love mathematics. Sajeeb has a fascination with ZERO. They are discussing a math problem. $M$ is equal to $A$ to the power $B$ multiply $C$ to the power $D$ multiply E to the power $F$. In mathematical equation:

M = A^B x C^D x E^F

Now, You are given six integers ($A$, $B$, $C$, $D$, $E$, $F$). You have to print the trailing zeros of $M$.

Input

The first line contains one integer $t$ ($1 \le t \le 10000$). Each of the next $t$ lines contains six integers: $A$, $B$, $C$, $D$, $E$ and $F$ ($0 \le A, B, C, D, E, F \le 1000000$).

Output

For each test case, print the case number as "Case X: " followed by the number of trailing zeros of $M$.

Sample

Input	Output
2 2 3 4 2 5 1 2 1 6 2 8 2	Case 1: 1 Case 2: 0