Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3246
Grid Point Counting

Time Limit: 7 Seconds      Memory Limit: 32768 KB

Task

You have a number of sticks, which are thin enough to be considered as segments on the XY plane.

Your task is simple: count the number of grid points that are covered by at least one segment.

Input

The first line contains a single integer T (T <= 10), the number of test cases. Each case begins with an integer n (1 <= n <= 500), the number of segments. Each of the following n lines contains four real numbers x1, y1, x2, y2, denoting a segment (x1,y1)-(x2,y2). All of x1, y1, x2, y2 will be no larger than 10000 in their absolute values, and will contain at most 4 digits after decimal point.

Output

For each test case, print the case number and the number of grid points.

Sample Input

2
2
-1 0 1 0
0 1 0 -1
1
1 2 3 4.0001

Sample Output

Case 1: 5
Case 2: 1

Author: Tang, Wenbin
Source: The 2009 ACM-ICPC Asia Ningbo Regional Online Contest
Submit    Status