KSEQ - 123 Sequence


A 123 sequence is defined as a non-decreasing sequence of length>=2, where each number is 1 or 2 or 3. The difference between all unique pairs of numbers is given i.e. for a 123 sequence a1, a2, a3, ... and the differences are aj-ai for 1 <= i < j <= n.

Since the 123 sequence contains only 1, 2, 3 the difference between any pair can be 0, 1, 2. Given the number of 0s, 1s, 2s in the difference sequence X, Y, Z respectively, your task is to find the number of distinct 123 sequences that could result in X, Y, Z.

Two 123 sequences A and B are considered different if there exists at least one i such that Ai is not equal to Bi.

Input

First line of the input contains the number of test cases T. (T <= 10000). Then follow T lines each containing 3 space separated integer X, Y, Z. (0 <= X, Y, Z <=108. X+Y+Z > 0).

Output

For each test case output the number of distinct 123 sequences in a separate line.

Example

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

Output:
1
0
2

Explanation

For the third test case the 123 sequences are 1, 2, 3, 3 and 1, 1, 2, 3.


hide comments
smso: 2022-03-17 07:07:20

Testcases with 123 sequences of length=7
16
21 0 0
15 6 0
11 10 0
9 12 0
15 0 6
10 6 5
7 10 4
6 12 3
7 12 2
10 10 1
11 0 10
7 6 8
5 10 6
5 12 4
9 0 12
6 6 9
3
4
4
4
2
2
2
2
2
1
2
2
2
1
2
1

Raghavendran Ramachandran: 2012-10-26 19:04:39

Interesting border cases.

Efim: 2011-07-12 22:30:55

Nice problem.


Added by:arun
Date:2010-01-02
Time limit:0.202s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Kurukshetra OPC 2010