1, 2, 3, 4

Time limit1sMemory limit256 MB

Summary

For each test case, count the distinct sums obtainable from up to a copies of 1, b copies of 2, c copies of 3, and d copies of 4.

Level: Medium6 of 10
Topics: Math, Greedy
Solved: No attempts yet

Problem

There are $a$ copies of $1$ , $b$ copies of $2$ , $c$ copies of $3$ , and $d$ copies of $4$ . Write a program that counts the number of distinct values that can be obtained by choosing zero or more of these numbers and adding them together. The sum when nothing is chosen is $0$ .

Input

The first line contains the number of test cases $T$ .

Each test case is given on one line as $a$ , $b$ , $c$ , and $d$ , separated by spaces.

Output

For each test case, print the answer on its own line.

Constraints

$1 \le T \le 100000$
$0 \le a, b, c, d \le 10^{17}$

Examples1

Example 1

Input

3
1 1 0 1
0 0 1 2
100000000000000000 100000000000000000 100000000000000000 100000000000000000

Expected output

8
6
1000000000000000001