Birthday Surprise Lights

Peter has designed a string of colorful lights as a birthday surprise for his girlfriend. The lights consist of a row of N independent bulbs, each of which can be either ON or OFF, which means there are at most 2^N possible configurations. However, due to technical limitations, there are only M switches available. Each switch controls a subset of bulbs in an irregular way – when a switch is pressed, it toggles (flips) the state of every bulb in its range (i.e. ON becomes OFF and OFF becomes ON). Initially, all bulbs are OFF. Given the range of bulbs that each switch controls (specified as a contiguous segment from L to R), your task is to compute how many different overall configurations (styles) the lights can demonstrate.

Mathematically, each switch can be seen as a vector in GF(2) (each bulb state is 0 or 1) and toggling corresponds to vector addition mod2. Since pressing a switch twice cancels its effect, each switch is either pressed or not pressed. The final configuration is the sum (mod2) of the selected switch vectors. The number of distinct configurations is 2^r, where r is the rank (over GF(2)) of these M vectors. In formula:

$$\text{Answer} = 2^{\text{rank}}.$$

inputFormat

The input begins with an integer T representing the number of test cases. Each test case is described as follows:

• The first line contains two integers N and M, where N is the number of bulbs and M is the number of switches.
• Each of the next M lines contains two integers L and R (1-indexed) indicating that the corresponding switch toggles the state of all bulbs from position L to R (inclusive).

outputFormat

For each test case output a single integer in a new line representing the number of distinct configurations that the lights can display.

sample

1
3 2
1 1
1 2

4