Painting is always a boring job.

There are blocks on an infinite two-dimensional plane. Each block is a rectangle parallel to the -axis and -axis with a non-zero area. 

The coordinates of bottom-left corner and top-right corner of the -th block are and . 

There is another block with coordinates of bottom-left corner and top-right corner are and . Nike wants to paint this block black. He will repeatedly choose one of the previous blocks uniformly at random and independently and fill it black, until the rectangle is completely filled black. 

Find the expected value of the number of times the procedure is done, modulo . If the procedure is impossible to stop, output .

输入描述:

The input contains several test cases, and the first line contains a positive integer  indicating the number of test cases which is up to .

For each test case, the first line contains an integer  ().

The second line contains  integers  ().

Each of the following  lines contains  integers  (, ), describing the coordinates according to the problem statement.

输出描述:

For each test case, output one line, the answer modulo . If the procedure is impossible to stop, output .

It can be proved that the expected value is always a rational number. Additionally, under the constraints of this problem, when that value is represented as  using two coprime integers  and , it can be proved that there uniquely exists an integer  such that  and . In this case, you should find this .

1
8
5 5
0 0 2 2
2 2 5 5
0 2 2 5
2 0 5 2
0 0 1 1
1 1 5 5
0 1 1 5
1 0 5 1

10