×

- 20.26%
- 8192K

There are $N$ light bulbs indexed from $0$ to $N-1$. Initially, all of them are off.

A FLIP operation switches the state of a contiguous subset of bulbs. $FLIP(L, R)$ means to flip all bulbs $x$ such that $L \leq x \leq R$. So for example, $FLIP(3, 5)$ means to flip bulbs $3$ , $4$ and $5$, and $FLIP(5, 5)$ means to flip bulb $5$.

Given the value of $N$ and a sequence of $M$ flips, count the number of light bulbs that will be on at the end state.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each test case starts with a line containing two integers $N$ and $M$, the number of light bulbs and the number of operations, respectively. Then, there are $M$ more lines, the $i$-th of which contains the two integers $L_i$ and $R_i$, indicating that the $i$-th operation would like to flip all the bulbs from $L_i$ to $R_i$ , inclusive.

$1 \leq T \leq 1000$

$1 \leq N \leq 10^6$

$1 \leq M \leq 1000$

$0 \leq L_i \leq R_i \leq N-1$

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from $1$) and $y$ is the number of light bulbs that will be on at the end state, as described above.

2 10 2 2 6 4 8 6 3 1 1 2 3 3 4

Case #1: 4 Case #2: 3