SIMEQN - A simple equation

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

Added by:Varun Jalan
Date:2010-01-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: PERL6
Resource:own problem

hide comments
2012-01-28 21:44:03 Mitch Schwartz
Haha, I wrote a solution for a+b+c==N because I didn't read carefully enough. a+b+c<=N is an inequality, not an equation.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.