Strange Square

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Small Jan and Rain are playing an interesting game: Strange Square. A stranger square is a square of numbers that is arranged such that every row and column has the same sum. For example:
1 2 3
3 2 1
2 2 2
Now, there are 9 numbers (-100000 <= xi <= 100000) and they want to know the number of distinct ways those numbers can be arranged in a strange square. Two squares are distinct if they differ in value at one or more positions.

Input

The input contains multiple test cases. The first line is the number of cases T (0 < T <= 100).
Each case contains a line with 9 numbers.

Output

You should output one line for each test case. The line contains the case number first, and then one integer indicating the number of distinct ways.

Sample Input

2
1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9


Sample Output

Case 1: 1
Case 2: 72


Source

2012年"浪潮杯"山东省第三届ACM大学生程序设计竞赛(热身赛)