Given N, A, B, C, find how many solutions exist to the equation : a + b + c <= N, such that 0 <= a <= A, 0 <= b <= B, 0 <= c <= C.

Input

The first line contains the number of test cases T. Each test case contains 4 integers, N, A, B, C. 0 <= N, A, B, C <= 2500.

Output

Output T lines, one for each test case.

Example

Input:
2
4 3 2 1
1 1 1 1

Output:
20
4