## Algorithm

A. A.M. Deviation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A number a2�2 is said to be the arithmetic mean of two numbers a1�1 and a3�3, if the following condition holds: a1+a3=2a2�1+�3=2⋅�2.

We define an arithmetic mean deviation of three numbers a1�1a2�2 and a3�3 as follows: d(a1,a2,a3)=|a1+a32a2|�(�1,�2,�3)=|�1+�3−2⋅�2|.

Arithmetic means a lot to Jeevan. He has three numbers a1�1a2�2 and a3�3 and he wants to minimize the arithmetic mean deviation d(a1,a2,a3)�(�1,�2,�3). To do so, he can perform the following operation any number of times (possibly zero):

• Choose i,j�,� from {1,2,3}{1,2,3} such that ij�≠� and increment ai�� by 11 and decrement aj�� by 11

Help Jeevan find out the minimum value of d(a1,a2,a3)�(�1,�2,�3) that can be obtained after applying the operation any number of times.

Input

The first line contains a single integer t (1t5000)(1≤�≤5000)  — the number of test cases.

The first and only line of each test case contains three integers a1�1a2�2 and a3�3 (1a1,a2,a3108)(1≤�1,�2,�3≤108).

Output

For each test case, output the minimum value of d(a1,a2,a3)�(�1,�2,�3) that can be obtained after applying the operation any number of times.

Example
input
Copy
3
3 4 5
2 2 6
1 6 5

output
Copy
0
1
0

Note

Note that after applying a few operations, the values of a1�1a2�2 and a3�3 may become negative.

In the first test case, 44 is already the Arithmetic Mean of 33 and 55.

d(3,4,5)=|3+524|=0�(3,4,5)=|3+5−2⋅4|=0

In the second test case, we can apply the following operation:

(2,2,6)(2,2,6) increment a2decrement a1→increment �2decrement �1 (1,3,6)(1,3,6)

d(1,3,6)=|1+623|=1�(1,3,6)=|1+6−2⋅3|=1

It can be proven that answer can not be improved any further.

In the third test case, we can apply the following operations:

(1,6,5)(1,6,5) increment a3decrement a2→increment �3decrement �2 (1,5,6)(1,5,6) increment a1decrement a2→increment �1decrement �2 (2,4,6)(2,4,6)

d(2,4,6)=|2+624|=0�(2,4,6)=|2+6−2⋅4|=0

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define endl '\n'
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin>>t;
while(t--){
int a, b, c;
cin>>a>>b>>c;
int diff = 2 * b - (a + c);
(diff % 3 == 0) ? cout<<0<<endl : cout<<1<<endl;
}

}
Copy The Code &

Input

cmd
3
3 4 5
2 2 6
1 6 5

Output

cmd
0
1
0