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 <= t <= 100

0 <= N, A, B, C <= 5000

** No other constraints are applicable.

Sample

Input
3
2 1 2 3
1 1 1 1
2 1 0 1

Output
9
4
4

Explanation

Explanation for the sample test case 1:

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, so 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.