Analyzing floor tiles is a newly trending hobby for Jakartan school children who are accustomed to decorated floor grids in various buildings, especially in Jakarta shopping malls. A curious child wonders: If she could reduce an infinitely- repeating patterns in a grid into the smallest possible unit, such that, when the unit is repeated without any overlap it could cover all the patterned cells without exception, what is the smallest possible unit size? For simplicity, we assume that each cell in the grid can be either blank or dotted. For example, given a tile pattern as shown in Figure 1. She can deduce that it indeed can be reproduced with a minimal unit of size 5 (Figure 2), such that the unit, if infinitely tiled without overlapping, can cover the whole pattern (Figure 3). Figure 2 Figure 3 Now we’re attempting to solve a more general problem. Suppose you are given the positions of every single dot in the infinite grid, described by: (DX1, DY 1), (DX2, DY 2), (DX3, DY 3) which means: Only the cells at position (X, Y ) that satisfies X = i ∗ DX1 + j ∗ DX2 + k ∗ DX3 and Y =i∗DY1+j∗DY2+k∗DY3 for some integers i, j, and k are dotted and the rest is blank. For example, given (DX1, DY 1) = (5, 1) (DX2, DY 2) = (−1, −5) (DX3, DY 3) = (2, 2) The pattern will look like Figure 4, and a tile with minimal size of 8 can reproduce the pattern as shown in Figure 5. Figure 1
2/3 Figure 4 Figure 5 Given the positions of the dotted cells in an infinite grid described by the manner above, what is the smallest unit size, that, if repeated as is (no mirroring, no rotation) without overlaps, can cover the pattern in the grid without leaving some cells uncovered? Input The first line contains the number of cases, T (1 ≤ T ≤ 1000). Each case consists of a line containing six integers: DX1, DY 1, DX2, DY 2, DX3, DY 3 (each integer is in the range -10000 to 10000, inclusive). It is guaranteed that the three vectors (DX1, DY 1), (DX2, DY 2), and (DX3, DY 3) all point to different directions (no vector is simply a scalar multiple of another vector). Output For each case, output ‘Case #X: Y ’, where X is case number starts from 1 and Y is the smallest number of cells in a unit that if infinitely repeated without overlap can cover the pattern in the grid. Notes: • Explanation for the 1st and 2nd sample input. These samples demonstrate two different ways to describe the first example in the problem state- ment. • Explanation for the 3rd sample input. This sample corresponds to the second example in the problem statement. • Explanation for the 4th sample input. This sample input corresponds to all cells dotted in the pattern, hence the minimum tile size is 1. Sample Input 4 1 2 2 -1 -5 0 2 4 7 4 -3 -1 5 1 -1 -5 2 2 122122
3/3 Sample Output Case #1: 5 Case #2: 5 Case #3: 8 Case #4: 1