# Multifactorials

A generalization of the factorials gives us multifactorials: n! = n ∗ (n − 1) ∗ (n − 2) ∗ (n − 3) . . . n!! = n ∗ (n − 2) ∗ (n − 4) ∗ (n − 6) . . . n!!! = n ∗ (n − 3) ∗ (n − 6) ∗ (n − 9) . . . In general (there are k marks ‘!’): n!! . . .! = n ∗ (n − k) ∗ (n − 2k) . . . (n mod k), if k doesn’t divide n, n!! . . .! = n ∗ (n − k) ∗ (n − 2k) . . . k, if k divides n It this problem you are given a multifactorial, and you have to find the number of different dividers it has. Input The first line contains integer N (0 < N ≤ 500), it is number of tests. Each of the next N lines contains a multifactorial. Integer part of multifactorial is less or equal to 1000 and there are no more then 20 characters ‘!’. Output For each test case print line formatted like this: ‘Case i: a’. Where i is a test number, and a is the number of dividers in multifactorial. If number of dividers exceed 1018 print ‘Infinity’ (see examples). Sample Input 3 5! 13!! 230! Sample Output Case 1: 16 Case 2: 64 Case 3: Infinity