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≤t≤10000). Each of the next t lines contains six integers: A, B, C, D, E and F (0≤A,B,C,D,E,F≤1000000).
Output
For each test case, print the case number as "Case X: " followed by the number of trailing zeros of M.