abc-garfield

Garfield the cat likes candies A LOT. He always keeps a huge stock of it at his home. Today John, his owner, brought home three types of candies. He brought A pieces of Red candy, B pieces of Green candy and C pieces of Blue candy. Garfield is really happy. But the problem is that John won’t allow him to eat all of it at once. He will allow him to eat at most N candies. Garfield is very confused. His love for candies is clouding his judgement and he can’t make a decision on how to choose the N candies. Garfield is a dumb cat. So he asks you to find out in how many ways he can choose from the available type of candies so that he eats a total of N candies or less. Note: There is no difference between candies of the same color

Input:

The first line contains an integer t, the number of test cases. Each test case contains four space separated integers N,A,B,C.

Output:

For each test case output a single line containing the number of ways Garfield can choose the N candies.

Constraints:

0 ≤ N,A,B,C ≤ 2500

SAMPLE INPUT
3
2 1 2 3
1 1 1 1
2 1 0 1

SAMPLE OUTPUT
9
4
4

Explanation

Explanation for the sample test case 2:

For the test case 2 1 2 3

There is 1 piece of Red candy, 2 pieces of Green and 3 pieces of Blue. Garfield can eat at most 2 candies.

the possible combinations are:

(R,G,B)

(0,0,0)

(0,0,1)

(0,0,2)

(0,1,1)

(1,0,1)

(0,1,0)

(0,2,0)

(1,1,0)

(1,0,0)

Therefore 9 is the answer.

Source: hackerearth | Difficulty: EASY


Solutions: