You are given the coordinates of a triangle lying on a 2D Cartesian plane. The whole plane can be divided into square blocks of 1 × 1 size. Your job is to find out how many of the 1 × 1 square blocks have at least 50% of its area inside the triangle. The picture below shows a triangle where the vertices are at (0, 1), (9, 3) and (3, 8). And the shaded squares are the squares with at least 50 Input The first line of the input contains an integer T (≤ 100) denoting the number of test cases. Each of the following T lines contain six space separated integers x1 y1 x2 y2 x3 y3 giving the coordinates of the triangle. The given coordinates will form a valid triangle with positive area and all the coordinates will be integers having values between 0 and 100 (inclusive). Output For each input, print the output in the format ‘Case X: Y ’ (here, X is the serial of the input and Y is the number of squares which have at least 50% of its area inside the triangle). Sample Input 2 019338 114114 Sample Output Case 1: 29 Case 2: 6