Stack likes the number 3 a lot. 

He has two non-negative integers A and B.  
In one operation, Stack can do either of the following:
A:=|A-B| (change A to |A-B|)
B:=|A-B| (change B to |A-B|)
 
Note that |X| denotes absolute value of X. For example |-7| = 7 and |4| = 4.

Find the minimum number of operations after which at least one integer out of A and B becomes divisible by 3.

------ Input Format ------ 

- The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
- The only line of each test case contains two integers A and B.

------ Output Format ------ 

For each test case, output in a single line the minimum number of operations after which at least one integer out of A and B becomes divisible by 3.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$0 ≤ A, B ≤ 10^{9}$

----- Sample Input 1 ------ 
2
0 343
1 1

----- Sample Output 1 ------ 
0
1

----- explanation 1 ------ 
Test case $1$: $A=0$ is already divisible by $3$.

Test case $2$: In the only operation, Stack can change $A=1$ to $A = |A-B| = |1-1| = 0$. Now $A=0$ is divisible by $3$.

Source: codechef | Difficulty: EASY
Tags: Mathematics


Solutions:
for i in range(int(input())):
	(a, b) = map(int, input().split())
	count = 0
	if a % 3 == 0 or b % 3 == 0:
		print('0')
	else:
		while a % 3 != 0 or b % 3 != 0:
			a1 = abs(a - b)
			a2 = abs(a - b)
			a = a1
			b = a2
			count += 1
		print(count)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	if a % 3 == 0 or b % 3 == 0:
		print(0)
	elif a % 3 == b % 3:
		print(1)
	elif a % 3 != b % 3:
		print(2)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	count = 0
	if a % 3 == 0 or b % 3 == 0:
		print('0')
	else:
		count = 0
		while a % 3 != 0 or b % 3 != 0:
			a1 = abs(a - b)
			b1 = abs(a - b)
			a = a1
			b = b1
			count = count + 1
		print(count)


T = int(input())
for _ in range(T):
	(A, B) = map(int, input().split())
	li = [A, B]
	count = 0
	while A % 3 != 0 and B % 3 != 0:
		if A > B:
			A = A - B
		else:
			B = B - A
		count += 1
	print(count)


t = int(input(''))
for i in range(t):
	(A, B) = map(int, input().split())
	if A % 3 == 0:
		print(0)
		continue
	if B % 3 == 0:
		print(0)
		continue
	if A % 3 == 1 and B % 3 == 1:
		print(1)
		continue
	if A % 3 == 1 and B % 3 == 2:
		print(2)
		continue
	if A % 3 == 2 and B % 3 == 1:
		print(2)
		continue
	if A % 3 == 2 and B % 3 == 2:
		print(1)
		continue


import sys
for _ in range(int(sys.stdin.readline())):
	(a, b) = map(int, sys.stdin.readline().split())
	if a % 3 == 0 or b % 3 == 0:
		print(0)
	elif a % 3 == b % 3:
		print(1)
	else:
		print(2)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	s = 0
	while a % 3 != 0 and b % 3 != 0:
		dif = abs(a - b)
		a = dif
		b = dif
		s += 1
	print(s)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = 0
	while a % 3 != 0 and b % 3 != 0:
		diff = abs(a - b)
		if a > b:
			a = diff
		else:
			b = diff
		c += 1
	print(c)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	i = 0
	while a % 3 != 0 and b % 3 != 0:
		x = abs(a - b)
		if a > b:
			a = x
		else:
			b = x
		i += 1
	print(i)


T = int(input())
for t in range(T):
	(A, B) = map(int, input().split())
	count = 0
	while A % 3 != 0 and B % 3 != 0:
		dif = abs(A - B)
		if A > B:
			A = dif
		else:
			B = dif
		count += 1
	print(count)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = 0
	while a % 3 != 0 and b % 3 != 0:
		s = abs(a - b)
		if a > b:
			a = s
		else:
			b = s
		c += 1
	print(c)


test = int(input())
for i in range(test):
	count = 0
	(a, b) = map(int, input().split())
	while a % 3 != 0 and b % 3 != 0:
		d = abs(a - b)
		if a > b:
			a = d
		else:
			b = d
		count += 1
	print(count)


T = int(input())
for _ in range(T):
	(A, B) = map(int, input().split())
	C = 0
	if A > B:
		(A, B) = (B, A)
	while A % 3 != 0 and B % 3 != 0:
		C += 1
		B = abs(A - B)
	print(C)


T = int(input())
for i in range(T):
	(A, B) = map(int, input().split())
	X = 0
	if A > B:
		(A, B) = (B, A)
	while A % 3 != 0 and B % 3 != 0:
		X += 1
		B = abs(A - B)
	print(X)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	s = 0
	while x % 3 != 0 and y % 3 != 0:
		diff = abs(x - y)
		if x > y:
			x = diff
		else:
			y = diff
		s += 1
	print(s)


t = int(input())
for z in range(t):
	(a, b) = map(int, input().split())
	op = 0
	while a % 3 != 0 and b % 3 != 0:
		c = abs(a - b)
		if a > b:
			a = c
		else:
			b = c
		op += 1
	print(op)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	count = 0
	while a % 3 != 0 and b % 3 != 0:
		z = abs(a - b)
		if a > b:
			a = z
		else:
			b = z
		count = count + 1
	print(count)


t = int(input())
while t > 0:
	(a, b) = map(int, input().split())
	count = 0
	if a > b:
		(a, b) = (b, a)
	while a % 3 != 0 and b % 3 != 0:
		b = abs(b - a)
		count += 1
	print(count)
	t -= 1


t = int(input())
for i in range(t):
	(a, b) = [int(x) for x in input().split()]
	if 0 <= a <= 10 ** 9 and 0 <= b <= 10 ** 9:
		cnt = 0
		while a % 3 != 0 and b % 3 != 0:
			diff = abs(a - b)
			if a > b:
				a = diff
			else:
				b = diff
			cnt += 1
		print(cnt)


Test = int(input())
for Cases in range(Test):
	(IntegarA, IntegarB) = map(int, input().split())
	Count = 0
	if IntegarA % 3 == 0 or IntegarB % 3 == 0:
		print('0')
	else:
		while IntegarA % 3 != 0 or IntegarB % 3 != 0:
			IntegarAResult = abs(IntegarA - IntegarB)
			IntegarBResult = abs(IntegarA - IntegarB)
			IntegarA = IntegarAResult
			IntegarB = IntegarBResult
			Count = Count + 1
		print(Count)


for _ in range(int(input())):
	(A, B) = map(int, input().split())
	n = 0
	if A % 3 == 0 or B % 3 == 0:
		print(0)
	else:
		while A % 3 != 0 or B % 3 != 0:
			a1 = abs(A - B)
			b1 = abs(B - A)
			A = a1
			B = b1
			n = n + 1
		print(n)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split(' '))
	n = 0
	if a % 3 == 0 or b % 3 == 0:
		print(0)
	else:
		while a % 3 != 0 or b % 3 != 0:
			a1 = abs(a - b)
			b1 = abs(a - b)
			a = a1
			b = b1
			n += 1
		print(n)


for i in range(int(input())):
	(a, b) = list(map(int, input().split()))
	num = 0
	if a % 3 == 0 or b % 3 == 0:
		print(0)
	else:
		while a % 3 != 0 or b % 3 != 0:
			a1 = abs(a - b)
			b1 = abs(a - b)
			a = a1
			b = b1
			num += 1
		print(num)


def min_operation(a, b):
	cout = 0
	while a % 3 != 0 and b % 3 != 0:
		diff = abs(a - b)
		if a > b:
			a = diff
		else:
			b = diff
		cout += 1
	return cout
for i in range(int(input())):
	(a, b) = map(int, input().split())
	print(min_operation(a, b))


test_cases = int(input())
for i in range(test_cases):
	(a, b) = map(int, input().split())
	operations = 0
	if a % 3 == 0 or b % 3 == 0:
		print(operations)
	else:
		while a % 3 != 0 and b % 3 != 0:
			diff = abs(a - b)
			if a >= b:
				a = diff
			else:
				b = diff
			operations += 1
		print(operations)


def get_count(A, B):
	count = 0
	while A % 3 != 0 and B % 3 != 0:
		sub = abs(A - B)
		if A > B:
			A = sub
		else:
			B = sub
		count += 1
	return count
for _ in range(int(input())):
	(A, B) = map(int, input().split())
	print(get_count(A, B))


for i in range(int(input())):
	(a, b) = list(map(int, input().split()))
	x = abs(a - b)
	y = abs(b - a)
	if a % 3 == 0 or b % 3 == 0:
		print('0')
	elif x % 3 == 0 or y % 3 == 0:
		print('1')
	else:
		print('2')


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	cn = 0
	while a % 3 != 0 and b % 3 != 0:
		d = abs(a - b)
		if a > b:
			a = d
		else:
			b = d
		cn += 1
	print(cn)


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	count = 0
	while x % 3 != 0 and y % 3 != 0:
		diff = abs(x - y)
		if x > y:
			x = diff
		else:
			y = diff
		count = count + 1
	print(count)


for i in range(int(input())):
	(A, B) = map(int, input().split())
	c = 0
	while A % 3 != 0 and B % 3 != 0:
		dif = abs(A - B)
		if A > B:
			A = dif
		else:
			B = dif
		c += 1
	print(c)


t = int(input())
for i in range(t):
	(A, B) = map(int, input().split())
	if A % 3 == 0 or B % 3 == 0:
		print(0)
	else:
		for n in range(1, min(A, B) + 2):
			C = abs(A - B)
			if C % 3 == 0:
				break
			n = n + 1
			if abs(A - C) % 3 == 0 or abs(B - C) % 3 == 0:
				break
		print(n)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a % 3 == 0 or b % 3 == 0:
		print(0)
	elif a % 3 == b % 3:
		print(1)
	else:
		print(2)


try:
	t = int(input())
	for r in range(t):
		(a, b) = map(int, input().split())
		if a % 3 == 0 or b % 3 == 0:
			print(0)
		elif abs(a - b) % 3 == 0:
			print(1)
		else:
			print(2)
except:
	pass


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	count = 0
	if a > b:
		(a, b) = (b, a)
	while a % 3 != 0 and b % 3 != 0:
		count += 1
		b = abs(a - b)
	print(count)