Melody is visiting the renowned Notre-Dame Basilica church in Montréal,
Canada. Aside from appreciating its beautiful architecture, she's there to see
a spectacular light show scheduled to be held within!

Representing the cross-sectional view of the church as a 2D plane, it has a
mirror-covered ceiling made up of two 45-degree line segments, the first
running from (0, 0) to (**H**, **H**) and the second running from (**H**,
**H**) to (2**H**, 0).

**N** lasers have been set up on the floor, pointing upwards, with the _i_th one at integral coordinates (**Xi**, 0) emitting a coloured beam of either red (if **Ci** = 1) or blue (if **Ci** = 2) light. All **N** lasers are at distinct positions, and there's no laser directly under the center of the ceiling (at x-coordinate **H**). If uninterrupted, each laser's beam travels vertically upwards until it hits a point on the ceiling, at which point it bounces to travel horizontally until it hits another point on the ceiling, at which point it bounces to travel vertically downwards and eventually hits another point on the floor. No laser has been set up such that its beam can possibly end up directly hitting another laser at the end of its path. In other words, if there's a laser at coordinates (x, 0), there's guaranteed to be no laser at coordinates (2**H** \- x, 0).

For example, if **H** = 5 and there's a single red laser at coordinates (7,
0), the church would look as follows:

![]({{PHOTO_ID:984673281988054}})

Melody thinks it looks pretty when laser beams interact with one another, but
not when red and blue beams clash, so she's going to take matters into her own
hands to optimize the show's appearance. She will use drones to suspend 0 or
more blockers in the air within the church, each occupying a single point
(possibly with non-integral coordinates) strictly above the x-axis and
strictly underneath the ceiling. Each laser beam stops traveling as soon as it
hits a blocker.

Let `I(i, j)` be true if lasers _i_ and _j_ intersect (in other words, if
there exists at least one point which both of their beams pass through). If
two laser beams hit the same blocker, they are not considered to intersect at
that blocker's coordinates. The quality **Q** of a light show, in Melody's
eyes, is the number of unordered pairs of laser beams (_i_, _j_) for which
`I(i, j)` is true and **Ci** = **Cj**. However, if there is any intersecting
pair of differently-coloured laser beams (i.e. there exists some pair of beams
(_i_, _j_) for which `I(i, j)` is true and **Ci** ≠ **Cj**), then the quality
of the light show is instead 0.

### Input

Input begins with an integer **T**, the number of light shows that Melody
watches. For each show, there is first a line containing the space-separated
integers **H** and **N**. Then, **N** lines follow, the _i_th of which
contains the space-separated integers **Xi** and **Ci**.

### Output

For the _i_th show, print a line containing "Case #_i_: " followed by a single
integer **Q**, the maximum possible quality of the light show.

### Constraints

1 ≤ **T** ≤ 150
2 ≤ **H** ≤ 1,000,000,000
1 ≤ **N** ≤ 4,000
1 ≤ **Xi** ≤ 2**H** \- 1
**Xi** ≠ **H**
1 ≤ **Ci** ≤ 2

### Explanation of Sample

In the first case, if no blockers are placed, all three unordered pairs of red
lasers will intersect with one another for a quality of 3:

![]({{PHOTO_ID:945646162539269}})

In the second case, if Melody were to place no blockers, there would be two
same-colour laser beam intersections (one involving the red lasers and another
involving the blue ones), but there would also be at least one different-
colour laser beam intersection, so this is not ideal as the quality is 0:

![]({{PHOTO_ID:282212846231841}})

If she instead places one blocker at coordinates (2.5, 1), blocking the first
laser, and another at (6, 2), blocking both both the second and fourth lasers,
then one same-colour laser beam intersection would be achieved (between the
second and third lasers at coordinates (7, 2)) for a quality of 1:

![]({{PHOTO_ID:711991349348175}})