Mr. Naruto is a super programmer and he is working for a company named SSK(Screen Systems of Konoha). The company assigned him a task, which is he has to create a screen where each pixel of the screen can hold multiple colors simultaneously. Here are the properties of the screen: • The screen is an M ×M square grid where each 1×1 square is a pixel. • The position of a pixel in the screen can be denoted by a (row,column) pair where 1 ≤ row, column ≤ M . • Intensity level of the pixel at position (row, column) is defined as the number of unique colors the pixel is colored with. Mr. Naruto successfully completed the task of constructing the screen and now he wants to do an experiment on the screen. • Each experiment can be denoted by four integers r c1 c2 c. • In each experiment, he selects a rectangular region consisting of pixels from row 1 to row r and from column c1 to column c2 of the screen. • Now he uses a special pen to paint each of the pixels in the screen at position (pr,pc) where 1≤pr ≤randc1 ≤pc ≤c2 withcolorc. After doing E such experiments, he is wondering about the intensity level of the pixels. You have to find how many pixels in the screen have an intensity level of at least L. Input The first line of input will contain an integer T (1 ≤ T ≤ 15) which is the number of test cases. The first line of each test case contains three space separated integers M (1 ≤ M ≤ 2 ∗ 109), E (1 ≤ E ≤ 105) and L (0 ≤ L ≤ 105). Where M is the screens side length, E is the number of experiments and L is the desired intensity level. Then following E lines each describes an experiment. Each experiment is denoted by four integers rc1 c2 c. Where1≤r≤M and1≤c1 ≤c2 ≤M. Andcwillbebetween1and105 (inclusive). There is a blank line after each test case in the input. Output For each case, print the case number and then the number of pixels in the screen having intensity level at least L. See sample output for the format. Sample Input 2 10 4 1 3261 4251 5482 3 7 10 3
2/2 10 4 2 3261 4251 5482 3 7 10 3 Sample Output Case 1: 39 Case 2: 17