Jingjing the panda lives in a forest containing n pieces of bam- boo land. Each bamboo land is very small and can be regarded as a single point. Bamboo land i contains Li bamboos and is associated with a “deliciousness” Wi. Jingjing eats all bamboos in a selected bamboo land every day. He has a bad habit: the deliciousness of the bamboo land he selects must be strictly larger than that of the day before. Moving from one land to another is very tiring. The longer Jingjing walks before arriving a bamboo land i, the more bamboo he is expecting. If the distance he walked from the last bamboo land is strictly larger than the number of bamboos he finds in the current land (i.e Li), he will die of sadness. Distance of two points (x0,y0) and (x1,y1) equals to |x0 − x1| + |y0 − y1|, since Jingjing only moves north, south, east and west. When you send Jingjing in one bamboo land someday, how many days can Jingjing survive (Jingjing is clever enough to find out the optimal way of living)? We need this information so that we can bring him out before he dies. Input The first line contains a single integer t (1 ≤ t ≤ 10), the number of test cases. Each test case contains several lines. The first line contains a single integer n (1 ≤ n ≤ 100,000), the number of bamboo lands. The next n lines each contains 4 integers Xi, Yi, Wi, Li, indicating the coordinate of i-th bamboo land, its deliciousness and number of bamboos. You may assume that 0 ≤ Xi,Yi,Wi,Li ≤ 1,000,000. No two lands have the same deliciousness. Two bamboo lands can be so close that they can be regarded as at the same point. Output For each test case, print the case number followed by the number of days Jingjing can survive. Look at the output for sample input for details. Sample Input 2 3 0034 2223 5513 3 0034 2223 5513
2/2 Sample Output Case 1: 2 Case 2: 2