The task is simple, on the 2D cartesian coordinate system, how many different shortest path from point O(0,0) to point A(x,y), but not through point B(x1,y1) and C(x2,y2).

Score is the length of your source.

Input

The first line is an integer T(1 ≤ T ≤ 10000), denoting the number of test cases. Then, T test cases follow.

Each test case consist of 3 lines:
-first line contains two integer x and y(1 ≤ x,y ≤ 10) location of point A
-second line contains two integer x1(0 ≤ x1 < x) and y1(1 ≤ y1 ≤ y) location of point B
-third line contains two integer x2(1 ≤ x2 ≤ x) and y2(0 ≤ y2 < y) location of point C

Output

For each test case, output number of different shortest path from (0,0) to point A but not through point B and C.

Example

Input:
2

4 5

3 4

2 2

3 3

2 1

1 2

Output:
32

2

See also: Another problem added by Tjandra Satria Gunawan