Having found out the marking scheme of our college, the aliens are infuriated and plan on bombing some strategic targets. But what they do not know is that our team of hackers was able to steal their attack plans. Think of our college as a 2-d grid of x and y coordinates, the admin being at 0, 0. The aliens will choose 2 coordinates in this grid and bomb all the points on the line joining those 2 points that have purely integral coordinates. For example, let’s say the aliens choose 2 points (0, 0) and (6, 10). This will have only 1 integer point on the line joining it. i.e. (3, 5).

The evil plan will fail if our hackers can get to know the count of these integral points.

Your task is simple. Help our hackers!

Input

First line of input will contain an integer t, the number of test cases. Following t lines will contain 4 space separated integers, x1, y1, x2, y2.

0 < t <= 1000

Absolute value of each coordinate is less than equal to 10^8.

Output

For each test case print the case number and then number of points that will be bombed as per the format of the sample test case.

Example

Input:
3
0 0 6 10
1 2 6 9
-3 -2 1 2

Output:
Case #1: 1
Case #2: 0
Case #3: 3