H - Multifactorials

Time Limit: 1 sec
Memory Limit: 16MB

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 10¹⁸ print "Infinity" (see examples).

SAMPLE INPUT:

3
5!
13!!
230!

SAMPLE OUTPUT:

Case 1: 16
Case 2: 64
Case 3: Infinity

Problem setters: Aleksej Viktorchik, Leonid Shishlo.
Huge Easy Contest #1