Alice has been given the responsibility of creating the background of the annual play in her school. The background consists of Mountains. One such Background-
Figure 1: A Cardboard Mountain Background.
The Mountains' characteristics are —
Mountains are triangles whose base is on the floor.
A stick is placed vertically from the floor to the peak of the mountain to support it.
The lower right vertex of a mountain starts from the stick of the mountain to the immediate left and the lower right vertex on the stick of the mountain to the immediate right.
The left-most mountain's lower left vertex is on the lower left corner of the background.
The right-most mountain's lower right vertex is on the lower right corner of the background.
The width of the stick is negligible.
Note that, a mountain is defined left (or, right) to another mountain if the stick supporting is strictly on the left (or, right respectively) of . Furthermore, is the immediate left (or, right) of if among all of the mountains who are on left (or, right) of , is the right-most (or, left-most respectively).
The Mountains are traditionally created this way. But Alice being a problem solver has thought of an easier way to create the mountains. Alice thought of doing the following —
Consider the background as a 2D Cartesian plane, where the lower left corner will be the origin and the lower right corner will be , where is the length of the background.
Fix the coordinates of the peaks of Mountains on the Cartesian plane, then draw the Mountains respecting their characteristics, on a paper for reference.
Cut a single cardboard shape according to that reference.
Let’s say Alice has generated 5 mountain peaks’ co-ordinates. They are , , , and . The length of the background is units. The final shape of the cardboard shape can be denoted by figure 1.
Alice is wondering what would be the area of the final cardboard shape for the Mountains on the background after cutting. Given the coordinates of the mountain tips, and the length of the background, , can you calculate the area of the final cardboard shape?
The first line contains a single integer , the number of test cases.
The first line of each test case contains two space-separated integers, and , denoting the number of peaks and the background’s length respectively.
The line of the next lines contain two integers and , the coordinate of the mountain.
The sum of all over test cases doesn’t exceed .
For each test case, output the area of the final cardboard shape. Your answer will be considered correct if the relative or absolute difference is less than . That means, if your answer is and jury’s answer is , your answer will be considered correct if .
1 5 25 8 6 18 14 4 10 13 12 22 8