A number $a_2$ is said to be the arithmetic mean of two numbers $a_1$ and $a_3$, if the following condition holds: $a_1 + a_3 = 2\cdot a_2$.

We define an arithmetic mean deviation of three numbers $a_1$, $a_2$ and $a_3$ as follows: $d(a_1, a_2, a_3) = |a_1 + a_3 - 2 \cdot a_2|$.

Arithmetic means a lot to Jeevan. He has three numbers $a_1$, $a_2$ and $a_3$ and he wants to minimize the arithmetic mean deviation $d(a_1, a_2, a_3)$. To do so, he can perform the following operation any number of times (possibly zero):

Choose $i, j$ from $\{1, 2, 3\}$ such that $i \ne j$ and increment $a_i$ by $1$ and decrement $a_j$ by $1$

Help Jeevan find out the minimum value of $d(a_1, a_2, a_3)$ that can be obtained after applying the operation any number of times.


-----Input-----

The first line contains a single integer $t$ $(1 \le t \le 5000)$  — the number of test cases.

The first and only line of each test case contains three integers $a_1$, $a_2$ and $a_3$ $(1 \le a_1, a_2, a_3 \le 10^{8})$.


-----Output-----

For each test case, output the minimum value of $d(a_1, a_2, a_3)$ that can be obtained after applying the operation any number of times.


-----Examples-----

Input
3
3 4 5
2 2 6
1 6 5
Output
0
1
0


-----Note-----

Note that after applying a few operations, the values of $a_1$, $a_2$ and $a_3$ may become negative.

In the first test case, $4$ is already the Arithmetic Mean of $3$ and $5$.

$d(3, 4, 5) = |3 + 5 - 2 \cdot 4| = 0$

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

$(2, 2, 6)$ $\xrightarrow[\text{increment $a_2$}]{\text{decrement $a_1$}}$ $(1, 3, 6)$

$d(1, 3, 6) = |1 + 6 - 2 \cdot 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)$ $\xrightarrow[\text{increment $a_3$}]{\text{decrement $a_2$}}$ $(1, 5, 6)$ $\xrightarrow[\text{increment $a_1$}]{\text{decrement $a_2$}}$ $(2, 4, 6)$

$d(2, 4, 6) = |2 + 6 - 2 \cdot 4| = 0$

Difficulty: EASY
Tags: Number theory

Mathematics

Starter code:

Solutions:
for s in [*open(0)][1:]:
	print(+(sum(map(int, s.split())) % 3 > 0))


import sys
T = int(sys.stdin.readline())
for r in range(T):
	(a, b, c) = map(int, sys.stdin.readline().split())
	D = abs(a + c - 2 * b)
	if D % 3 == 0:
		print(0)
	else:
		print(1)


import sys
input = lambda : sys.stdin.readline().strip()

def solve():
	(a, b, c) = map(int, input().split())
	for (x, y) in ((a + b, 2 * c), (a + c, 2 * b), (b + c, 2 * a)):
		if abs(x - y) % 3 == 0:
			return 0
	return 1
for _ in range(int(input())):
	print(solve())


import sys
for _ in range(int(sys.stdin.readline())):
	(a, b, c) = [int(x) for x in sys.stdin.readline().split()]
	if (a + b + c) % 3 == 0:
		print(0)
	else:
		print(1)


import sys

def solve():
	N = int(sys.stdin.readline().rstrip())
	for _ in range(N):
		(a, b, c) = list(map(int, sys.stdin.readline().rstrip().split(' ')))
		D = a + c - b * 2
		print(0 if abs(D) % 3 == 0 else 1)
solve()


import sys
import math
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def meanDev(x1, x2, x3):
	return abs(x1 + x3 - 2 * x2)

def deviation(case):
	x1 = case[0]
	x2 = case[1]
	x3 = case[2]
	if (x1 + x2 + x3) % 3 == 0:
		return 0
	else:
		return 1
res = []
iter = inp()
i = 0
while i < iter:
	case = inlt()
	test = deviation(case)
	res.append(test)
	i += 1
for r in res:
	print(r)


import math
from sys import stdin
from collections import Counter, deque
input = stdin.readline
for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	avg = (a + c) / 2
	if b != avg:
		if abs(b - avg) % 1.5 == 0:
			print(0)
		else:
			print(1)
	else:
		print(0)


import sys
ans = []
t = int(sys.stdin.readline())
for _ in range(t):
	(a, b, c) = map(int, sys.stdin.readline().split())
	(x, y, z) = (a + b - 2 * c, a + c - 2 * b, c + b - 2 * a)
	if x % 3 == 0 or y % 3 == 0 or z % 3 == 0:
		ans.append('0')
	else:
		ans.append('1')
print('\n'.join(ans))


import sys
input = sys.stdin.readline
t = int(input())
while t > 0:
	nums = [int(x) for x in input().split(' ')]
	a = nums[0] + nums[1]
	b = 2 * nums[2]
	if a >= b:
		if (a - b) % 3 == 0:
			print('0')
		else:
			print('1')
	elif b > a:
		if (b - a) % 3 == 0:
			print('0')
		else:
			print('1')
	t -= 1


t = int(input())
ret = []
for i in range(t):
	(a, b, c) = map(int, input().split())
	d = a + c - 2 * b
	if d <= 0:
		ret.append(min(1, abs(d) % 3))
	else:
		ret.append(min(d % 3, 1))
print(*ret, sep='\n')


import sys
inp = sys.stdin.readline()
test = int(inp.strip('\n'))
result = ''
for i in range(test):
	inp = sys.stdin.readline()
	l = list(map(int, inp.strip('\n').split()))
	(a, b, c) = l
	diff = abs(a + c - 2 * b)
	diff = diff % 3
	if diff == 2:
		diff = 1
	sys.stdout.write(str(diff) + '\n')


import itertools
from math import floor, log, log2, ceil
from itertools import groupby
import sys
t = int(input())
res = []
for i in range(t):
	[a1, a2, a3] = list(map(int, input().split()))
	res.append(abs(a3 + a1 - 2 * a2) % 3)
	if res[i] == 2:
		res[i] = 1
for i in range(t):
	print(res[i])


import sys
case = int(sys.stdin.readline())
for i in range(case):
	arr = list(map(int, sys.stdin.readline().split()))
	n1 = arr[0]
	n2 = arr[1]
	n3 = arr[2]
	d1 = n2 - n1
	d2 = n3 - n2
	if abs(d1 - d2) % 3 == 0:
		print(0)
	else:
		print(1)


import sys
for __ in range(int(input())):
	(a, b, c) = map(int, sys.stdin.readline().split())
	s = a + c - b * 2
	s = abs(s)
	print(min(s % 3, 3 - s % 3))


def function(t, tests):
	out = []
	for case in tests:
		a1 = int(case[0])
		a2 = int(case[1])
		a3 = int(case[2])
		d = abs(a3 + a1 - 2 * a2)
		if d % 3 == 0:
			out.append('0')
		else:
			out.append('1')
	return '\n'.join(out)
t = int(input())
tests = []
for i in range(t):
	case = input().split()
	tests.append(case)
ans = function(t, tests)
print(ans)


import sys
import bisect
import math
input = lambda : sys.stdin.readline().strip()
mod = 10 ** 9 + 9

def solve():
	(a1, a2, a3) = map(int, input().split())
	if abs(a1 + a3 - 2 * a2) % 3 == 0:
		return 0
	else:
		return 1
t = 1
t = int(input())
for _ in range(t):
	print(solve())


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	a = [int(i) for i in input().split()]
	if sum(a) % 3:
		print(1)
	else:
		print(0)


t = int(input())
a = [0] * t
for i in range(t):
	l = list(map(int, input().split()))
	a[i] = abs(l[0] + l[2] - 2 * l[1]) % 3
	if a[i] == 2:
		a[i] = 1
for i in a:
	print(i)


for i in [*open(0)][1:]:
	print(+(sum(map(int, i.split())) % 3 > 0))


import sys
input = sys.stdin.readline

def solve(a1, a2, a3):
	(a1, a2, a3) = sorted([a1, a2, a3])
	d = abs(a1 + a3 - 2 * a2)
	(r1, r2) = (d % 3, 3 - d % 3)
	print(min(r1, r2))
for _ in range(int(input())):
	(a1, a2, a3) = map(int, input().split())
	solve(a1, a2, a3)


import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI1(rows_number):
	return [LI1() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline().rstrip()
dij = [(0, 1), (1, 0), (0, -1), (-1, 0)]
inf = 4294967295
md = 998244353

def solve():
	abc = LI()
	if sum(abc) % 3:
		print(1)
	else:
		print(0)
for testcase in range(II()):
	solve()


t = int(input())
for i in range(t):
	(a, b, c) = map(int, input().split())
	x = a + b + c
	if x % 3 == 0:
		print(0)
	else:
		print(1)


import sys
inp = sys.stdin.readline

def solve():
	(a, b, c) = map(int, input().split())
	r = a + c - 2 * b
	if r % 3 == 0:
		print(0)
	else:
		print(1)

def main():
	for i in range(int(inp())):
		solve()
main()


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
mod1 = 1000000000 + 7
mod2 = 998244353
sys.setrecursionlimit(10000000)
for _ in range(I()):
	(a1, a2, a3) = M()
	if abs(a1 + a3 - 2 * a2) % 3 == 0:
		print(0)
	else:
		print(1)


n = int(input())
for i in range(n):
	summa = 0
	(a, b, c) = map(int, input().split())
	summa += a + b + c
	if summa % 3:
		print('1')
	else:
		print('0')


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	k = 2 * b - (a + c)
	if k % 3 == 0:
		print(0)
	else:
		print(1)


for i in range(int(input())):
	print(1 if sum(map(int, input().split())) % 3 else 0)


t = int(input())
for _ in range(t):
	(a, b, c) = list(map(int, input().split()))
	if abs(a + c - 2 * b) % 3 == 0:
		print(0)
	else:
		print(1)


n = int(input())
number = []
for i in range(n):
	number.append([int(x) for x in input().split()])
for i in range(n):
	q = number[i][0] + number[i][1] - 2 * number[i][2]
	w = number[i][0] + number[i][2] - 2 * number[i][1]
	e = number[i][2] + number[i][1] - 2 * number[i][0]
	if min(abs(q), abs(w), abs(e)) % 3 == 0:
		print('0')
	elif min(abs(q), abs(w), abs(e)) % 3 == 2:
		print('1')
	else:
		print('1')


a = eval(input())
c = []
for i in range(a):
	num = [int(n) for n in input().split()]
	d = 0
	if sum(num) % 3 == 0:
		c.append(0)
	else:
		c.append(1)
for i in c:
	print(i)


for i in range(int(input())):
	b = input().split()
	c = int(b[0]) + int(b[2])
	d = int(b[1]) * 2
	e = abs(c - d)
	print(min(1, e % 3))


t = int(input())
while t:
	(a, b, c) = map(int, input().split())
	if (a + b + c) % 3 == 0:
		print(0)
	else:
		print(1)
	t -= 1


i = int(input())
a = []
for s in range(i):
	t = input()
	a.append(list(map(int, t.split())))
for i in a:
	f = i[0] + i[-1] - i[1] * 2
	if f % 3 == 0:
		f = 0
	else:
		f = 1
	print(f)


t = int(input())
for _ in range(t):
	(a1, a2, a3) = map(int, input().split())
	s = a1 + a2 + a3
	print('1' if s % 3 else '0')


x = int(input())
for i in range(x):
	(y, z, n) = input().split()
	if int(y + z + n) % 3 == 0:
		print(0)
	else:
		print(1)


for _ in range(int(input())):
	(a, b, c) = list(map(int, input().strip().split()))
	if (a + b + c) % 3 == 0:
		print(0)
	else:
		print(1)


for _ in range(int(input())):
	a = list(map(int, input().split()))
	print(0 if (a[0] + a[1] - 2 * a[2]) % 3 == 0 else 1)


n = int(input())
for i in range(n):
	x = input()
	l = []
	l = x.split()
	a = int(l[0])
	b = int(l[1])
	c = int(l[2])
	if (a + b - 2 * c) % 3 == 0 or (a + c - 2 * b) % 3 == 0 or (b + c - 2 * a) % 3 == 0:
		print(0)
	else:
		print(1)


t = int(input())
for _ in range(t):
	(a1, a2, a3) = list(map(int, input().strip().split()))
	print(0) if (a1 + a3 - 2 * a2) % 3 == 0 else print(1)


t = int(input())
for i in range(t):
	(a1, a2, a3) = input().split(' ')
	a1 = int(a1)
	a2 = int(a2)
	a3 = int(a3)
	if (a1 + a3 - 2 * a2) % 3 == 0:
		print(0)
	else:
		print(1)


from sys import stdin
MOD = 10000000000.0 + 7

def rl() -> str:
	return stdin.readline().rstrip()

def ri() -> str:
	return int(rl())

def rii() -> str:
	return list(map(int, rl().split()))

def form(mean, dev):
	return abs(mean - dev)
t = ri()
for _ in range(t):
	(a, b, c) = rii()
	mean = a + c
	dev = b * 2
	ans = form(mean, dev) % 3
	if ans == 2:
		print(1)
	else:
		print(ans)


anslist = []
for i in range(int(input())):
	s = int(sum(map(int, input().split())))
	if s % 3 == 0:
		anslist.append(0)
	else:
		anslist.append(1)
	print(anslist[i])


_ = int(input())
for __ in range(_):
	(a, b, c) = map(int, input().split())
	d = abs(2 * b - (a + c))
	if not d:
		print(0)
		continue
	if d % 3 == 0:
		print(0)
		continue
	else:
		print(1)
		continue


inp1 = int(input())
for i in range(inp1):
	(a, b, c) = input().split()
	a = int(a)
	b = int(b)
	c = int(c)
	if (a + b + c) % 3 == 0:
		print(0)
	else:
		print(1)


t = int(input().strip())
re = 0
for _ in range(t):
	l = input().split(' ')
	(l[0], l[1], l[2]) = (int(l[0]), int(l[1]), int(l[2]))
	re = sum(l)
	if re % 3 == 0:
		print(0)
	else:
		print(1)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007

def solve(a, b, c):
	if abs(a + c - 2 * b) % 3 == 0:
		return 0
	return 1
t = inp()
res = []
for i in range(t):
	(a, b, c) = mul()
	res.append(solve(a, b, c))
for i in res:
	print(i)


import math
T = int(input())
for _ in range(T):
	(a1, a2, a3) = map(int, input().split())
	if (a1 + a2 + a3) % 3 == 0:
		print(0)
	else:
		print(1)


for i_ in range(int(input())):
	(a, b, c) = map(int, input().split())
	if (a + b + c) % 3 == 0:
		print(0)
	else:
		print(1)


t = int(input())
for _ in range(t):
	(a, b, c) = map(int, input().split())
	if (a + b + c) % 3 == 0:
		print(0)
		continue
	print(1)


t = int(input())

def arthmean(x, y, z):
	return abs(x + z - 2 * y)
for i in range(t):
	(a1, a2, a3) = map(int, input().split())
	if arthmean(a1, a2, a3) % 3 == 0:
		print(0)
	else:
		print(1)


import math
import sys
import itertools
import fractions
wtf = sys.stdin.read()
wtf = wtf.strip().split('\n')
for t in wtf[1:]:
	(a1, a2, a3) = map(int, t.split())
	print(0 if (a1 + a2 + a3) % 3 == 0 else 1)


mod = 10000000
for _ in range(int(input())):
	(a1, a2, a3) = map(int, input().split())
	if (a1 + a3 - 2 * a2) % 3 == 0:
		print(0)
	else:
		print(1)


for t in range(int(input())):
	(n1, n2, n3) = list(map(int, str.split(input())))
	S = n1 + n2 + n3
	if S % 3 == 0:
		print(0)
	else:
		print(1)


t = int(input())
for i in range(t):
	(a, b, c) = map(int, input().split())
	res = abs(a + c - 2 * b)
	res = res % 3
	if res == 2:
		res = 1
	print(res % 3)


for _ in range(int(input())):
	w = [int(i) for i in input().split()]
	if sum(w) % 3 == 0:
		print(0)
	else:
		print(1)


p = int(input())
for i in range(p):
	(a, b, c) = map(int, input().split())
	dif = 2 * b - (a + c)
	if dif % 3 == 0:
		print('0')
	else:
		print('1')


c = int(input())
for i in range(c):
	a = [int(s) for s in input().split()]
	(x, y, z) = (a[0], a[1], a[2])
	c = abs(x + z - 2 * y) % 3
	if c == 2:
		c = 1
	print(c)


t = int(input())
for j in range(t):
	(x, y, z) = map(int, input().split())
	if (x + y + z) % 3 == 0:
		print(0)
	else:
		print(1)