Given an integer $n$, you can perform the following two operations:

• $n \leftarrow n+1$, which increases $n$ by $1$.
• $n \leftarrow -n$, which multiplies $n$ by $-1$.

You are required to perform the first operation $a$ times and the second operation $b$ times in any order. Let $m$ be the maximum value of $|n|$ during the process. You need to minimize $m$ and output this minimum value.

Input

This problem contains multiple test cases.

The first line of input contains two non-negative integers $c$ and $t$, representing the test case ID and the number of test cases, respectively. $c=0$ indicates that the test case is a sample.

Each test case is described by a single line containing three integers $n, a, b$.

Output

For each test case:

• Output a single line containing an integer, representing the minimum value of $m$.

Examples

Input 1

0 5
0 5 1
0 6 2
0 114 514
250 5000 200
-13831 114514 1919810

Output 1

2
2
1
250
13831

Note 1

This sample contains $5$ test cases.

• For the first test case, performing operations of type $1, 2, 1, 1, 1$ in order yields the result.
• For the second test case, performing operations of type $1, 2, 1, 1, 2, 1$ in order yields the result.

Constraints

For all test cases:

• $1 \le t \le 10^5$;
• $0 \le |n|, a, b \le 10^9$.

• Special Property A: Guaranteed $a + b \le 10$.
• Special Property B: Guaranteed $n \ge 0$.
• Special Property C: Guaranteed $n = 0$.
• Special Property D: Guaranteed $n \le 0$.
• Special Property E: Guaranteed $t \le 100$.