There is a rectangle of n * m units. Another rectangle of a * b units is cut off from the upper right corner. Count the number of ways an ant can reach the bottom right corner starting from the top left corner, if it can move along the grid lines only right or down.

Input

The first line contains the number of test cases t. Each of the next t lines contains four integers n, m, a, b (2 ≤ n, m ≤ 400000, 1 ≤ a < n, 1 ≤ b < m).

Output

For each test case print on a separate line the number of ways an ant can reach the bottom right corner under the given conditions.