10041_堆禾草

奶牛Bessie对其过去的恶搞造成的影响感到内疚，所以主动帮农民John把干禾草堆起来。一开始有N ( 1 ≤ N ≤ 1000000, N 是奇数 )个空草堆，分别编号为1，2，...，N。John给她下达了K ( 1 ≤ K ≤ 25000 )个指令，指令的格式是"A B"，意思是叫Bessie把编号A到编号B范围里的所有草堆都叠上一捆禾草。例如，Bessie接到指令"10 13"，那么她就为草堆10、11、12、13各叠加上一捆禾草。当Bessie根据农民John的指令完成工作后，John想知道N堆草的高度的中位数，也就是说，如果按高度把这些草堆排序，他要知道中间那堆草的高度（N是奇数，所以肯定有中间的一堆草）。

有多个测试用例，第一行是一个整数T，表示测试用例的个数。

每个测试用例的第一行是两个整数 N 和 K。第二行开始共K行，每行是两个整数A和B ( 1 ≤ A ≤ B ≤ N )，表示John的一条指令。

为每个测试用例输出一行结果：Bessie完成指令后的各草堆高度的中位数。

1
7 4
5 5
2 4
4 6
3 5

1

共有7个堆，4条指令。第一条指令是在第5号堆叠加一捆禾草，第二条指令是在第2、3、4号堆上都叠加一捆禾草，如此类推。

Bessie完成所有指令后，各草堆的高度是0，1，2，3，3，1，0。草堆的中位数是1，因为按高度排序后的草堆分别是0，0，1，1，2，3，3，中位数是1。