Fouad

The ACPC steering committee decided to give the top 7 teams of the national contest prizes of equal value, and to write the total prize amount on the sponsor banner. The amount on the banner is spelled with 3D digit props placed next to each other. Abdulrahman Jamal Abouelkhair found the few digit props that were left in the nearby stores and bought all of them without asking. Mohamed Fouad, the deputy regional director, decided that none of the props will be thrown away.

So the amount written on the banner has to use every prop that was bought exactly once, and it has to be divisible by 7 for the 7 teams to receive equal shares. Count how many multiples of 7 can be built from all of the given digits.

The first digit of the number cannot be 0. The one exception is a set of props that is a single 0: that forms the number 0, and it counts as valid. If repeated props make two arrangements that differ in layout but have the same value, count that value once.

The first line contains one integer $T$, the number of test cases ($1 \le T \le 100$).

Each of the next $T$ lines holds one test case: a string of the digits to use. The string has length between 1 and 9, and every character is a digit from '0' to '9'. The string may start with 0.

For each test case print one line in the format Case n: R, where $n$ is the test case number starting from 1 and $R$ is how many multiples of 7 can be built from all of that test case's digits.