Traveler has just stolen Furina's favorite dessert, and now Furina is frantically searching for the damn traveler in the whole Fontaine!

Fontaine is a country composed of grids of  rows and  columns with rows numbered  and columns numbered . Our poor traveler is now in the grid with coordinate  at time , and expacts to reach the grid with coordinate  so that he could escape from Fontaine. During each moment, traveler can only move downwards or rightwords for any number of grids.

In order to catch traveler, Furina calls  inspectors who are scheduled to reach  at  to catch traveler, as long as traveler arrives, passes through, or leaves when or after , he will be caught! In addtion, Furina will close the gate of Fontaine after time , if traveler haven't escaped before that, he will never be able to escape!

However, traveler is a math lover, so in any cases of crisis, as long as not being caught, he'd like to figure out his fastest scheme to escape, and how many schemes are there in total.

Annotation：Different travel schemes are distinguished based on the direction and distance of escaping, which is not required to be identical every moments. For instance, even if the route is the same, a difference in the execution can still result in distinct schemes.

输入描述:

This question has multiple sets of test data.

The first line is an integer  (), representing the number of test cases.

For each test case, the first row of each set of data is  (),  () , (),  (), as described in the above question. In the following  line, there are three numbers  (， , )  in each line, representing the coordinates and arrival time of each inspectors.

输出描述:

For each set of data, output one line with two numbers. The first represents the number of schemes to escape, while the second represents the fastest speed's time to escape. Due to the conscience of the questioner, you only need to output the number of solutions afrer taking the modulus of . If unable to escape anyway, output only .

2
2 3 2 5
1 3 1
2 2 3
2 3 2 5
1 3 1
2 2 2

1 2
-1

As for the first test case, the situation are mapped below, where T represents traveler and F represents the finish line:

As for the first step, traveler can move downside to the end as mapped below as mapped below:

Then, if traveler don't move rightside to the end, the other inspector will arrived when traveler are trying to escape to the finish point, so there is only one possible schemea for him, and the fastest time is .

As for the second test case, the situation are mapped below:
As for the first step, traveler can move downside to the end as mapped below, and then there comes another inspector as mapped below:

Then, it can be proven that he can't reach the finish point anyway, so output .

1
8 8 11 8
7 4 2
3 1 2
1 8 1
2 1 1
5 4 1
5 8 3
8 5 4
7 1 1
3 6 1
7 2 1
1 7 2

7763 3

备注:

it is also guaranteed that grids  and  has no inspectors, but two or even more inspectors might appear in the same grid.