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 a₁, a₂, a₃, ... and the differences are a_j-a_i 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 A_i is not equal to B_i.

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 <=10⁸. 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.