# Bulb inside a Grid (II)

You are given a grid of size N × N . Each cell in the grid incorporates a bulb which can be initially on or off depending on its position. A bulb located at i-th row and j-th column will be initially off if i < j otherwise it will be on. The following figure shows a grid of dimension 6 × 6 in its initial configuration. 100000 110000 111000 111100 111110 111111 Here ‘1’ indicates on state and ‘0’ indicates off state. A switch can cover a rectangular region in the grid. A switch, when pressed, toggles all the bulbs in its corresponding region (that is, all the bulbs that are on goes off and vice versa). A switch is represented by four integers (row, column, width, height) where (row, column) denotes the top-left corner of the rectangular region and width & height are self-explanatory. Here is a diagram that should extricate things. The diagram shows a grid of size 6 × 6 with 3 switches in action. There are 3 switches; (4, 3, 2, 2), (5, 5, 4, 4) and (2, 5, 3, 2). Note that the regions wrap around and they can also overlap. Given the dimension of the grid, the number of switches in action, can you find out the number of bulbs that are on at the end? Input The first line of input is an integer T (T ≤ 25) that indicates the total number of test cases. Each case starts with two integers N (1 ≤ N ≤ 30, 000) and M (1 ≤ M ≤ 30, 000). N indicates the size of the grid and M specifies the total number of switches. Each of the following M lines gives the information of a switch. The information for a switch is represented by four integer values row, column, width, height. Here (1 ≤ row, column, width, height ≤ N ). Output For each case, print the case number followed by the total number of bulbs that are on after all the switches are pressed. Note that the order in which the switches are pressed is extraneous for the final outcome and therefore its intentionally not stated.

2/2 Sample Input 3 60 63 4322 5544 2532 1000 1 1 100 5 5 Sample Output Case 1: 21 Case 2: 13 Case 3: 500525