Meliodas and Ban are fighting over chocolates. Meliodas has $X$ chocolates, while Ban has $Y$. Whoever has lesser number of chocolates eats as many chocolates as he has from the other's collection. This eatfest war continues till either they have the same number of chocolates, or atleast one of them is left with no chocolates.

Can you help Elizabeth predict the total no of chocolates they'll be left with at the end of their war?

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, which contains two integers $X, Y$, the no of chocolates Meliodas and Ban have, respectively. 

-----Output:-----
For each testcase, output in a single line the no of chocolates that remain after Ban and Meliodas stop fighting.

-----Constraints-----
- $1 \leq T \leq 100000$
- $0 \leq X,Y \leq 10^9$

-----Sample Input:-----
3

5 3

10 10

4 8  

-----Sample Output:-----
2

20

8  

-----EXPLANATION:-----
Denoting Meliodas as $M$, Ban as $B$.
Testcase 1:
$M$=5, $B$=3

Ban eates 3 chocolates of Meliodas.
$M$=2, $B$=3

Meliodas eats 2 chocolates of Ban.
$M$=2, $B$=1

Ban eates 1 chocolate of Meliodas.
$M$=1, $B$=1

Since they have the same no of candies, they stop quarreling.

Total candies left: 2  
Testcase 2:
$M$=10, $B$=10

Since both of them had the same candies to begin with, there was no point in fighting.

Total candies left: 20  
Testcase 3:
$M$=4, $B$=8

Meliodas eats 4 chocolates of Ban.
$M$=4, $B$=4

Since they have the same no of candies, they stop quarreling.

Total candies left: 8

Source: codechef | Difficulty: EASY
Tags: Mathematics

Number theory

Implementation

Complete search


Solutions:
import math
x = int(input())
while x != 0:
	(y, z) = map(int, input().split())
	k = math.gcd(y, z)
	print(2 * k)
	x -= 1


import math
t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	print(math.gcd(x, y) * 2)


from math import gcd
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(2 * gcd(a, b))


import math
t = int(input())
for i in range(t):
	(M, B) = map(int, input().split(' '))
	m = M
	b = B
	gcd = 0
	gcd = math.gcd(m, b)
	print(2 * gcd)


import math
t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	if math.gcd(x, y) == 1:
		print('2')
	else:
		print(math.gcd(x, y) * 2)


t = int(input())
l = list()
k = 0
while t > 0:
	l = list(map(int, input().split()))
	l.sort()
	while l[0] != 0:
		if l[0] == l[1]:
			break
		if l[1] // l[0] * l[0] != l[1]:
			l[1] = l[1] - l[1] // l[0] * l[0]
		else:
			l[1] = l[1] - (l[1] // l[0] - 1) * l[0]
		l.sort()
	print(l[1] + l[0])
	t -= 1


def gc(a, b):
	return a * 2 if b == 0 else gc(b, a % b)
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if x > y:
		print(gc(x, y))
	else:
		print(gc(y, x))


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if n == m or n == 0 or m == 0:
		print(n + m)
	else:
		x = math.gcd(n, m)
		print(2 * x)


for i in range(int(input())):
	(X, Y) = map(int, input().split())
	while X != Y:
		if Y > X:
			(X, Y) = (Y, X)
		if X % Y == 0:
			X = Y
		else:
			X = X - X // Y * Y
	print(X + Y)


n = int(input())
for i in range(n):
	l = [int(x) for x in input().split()]
	(a, b) = (l[0], l[1])
	while True:
		if a == b or a == 0 or b == 0:
			break
		if a > b:
			if a % b == 0:
				a = b
			else:
				a = a % b
		elif b % a == 0:
			b = a
		else:
			b = b % a
	print(a + b)


t = int(input())
while t:
	(X, Y) = map(int, input().split())
	while X > 0 and Y > 0:
		if X > Y:
			if X % Y == 0:
				X = Y
				break
			X = X % Y
		else:
			if Y % X == 0:
				Y = X
				break
			Y = Y % X
	print(X + Y)
	t = t - 1


t = int(input())
for t in range(t):
	(x, y) = [int(i) for i in input().split()]
	if x > y:
		if x % y == 0:
			x = y
		else:
			x = x % y
	elif y > x:
		if y % x == 0:
			y = x
		else:
			y = y % x
	while x != y:
		if x < y:
			y = y - x
		else:
			x = x - y
	print(x + y)


tests = int(input())
for i in range(tests):
	(x, y) = map(int, input().split())
	if x == 0 or y == 0:
		print(x + y)
	else:
		while x != y and x > 0 and (y > 0):
			minimum = min(x, y)
			maximum = max(x, y)
			mod_val = maximum % minimum
			if mod_val == 0:
				x = minimum
				y = minimum
			elif x == minimum:
				y = mod_val
			else:
				x = mod_val
		print(x + y)


import math
T = int(input())
for t in range(T):
	input_arr = str(input()).split(' ')
	X = int(input_arr[0])
	Y = int(input_arr[1])
	print(2 * math.gcd(X, Y))


from math import gcd
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if x == y:
		print(x + y)
	else:
		print(2 * gcd(x, y))


from collections import Counter
t = int(input())

def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)
for _ in range(t):
	(x, y) = map(int, input().split())
	print(2 * gcd(x, y))


import math
for i in range(int(input())):
	(n, m) = map(int, input().split())
	if n == m or n == 0 or m == 0:
		print(n + m)
	else:
		a = math.gcd(n, m)
		print(2 * a)


import math
n = int(input())
while n > 0:
	list1 = []
	for i in input().split():
		list1.append(int(i))
	M = list1[0]
	B = list1[1]
	val = math.gcd(M, B)
	print(2 * val)
	n -= 1


def gcd(m, b):
	if m == 0:
		return b
	return gcd(b % m, m)
test = int(input())
while test != 0:
	(m, b) = list(map(int, input().split()))
	result = gcd(m, b)
	print(result * 2)
	test -= 1


t = int(input())
while t > 0:
	(x, y) = map(int, input().split())
	while x != y and (x != 0 and y != 0):
		if x > y:
			if x % y == 0:
				x = y
			else:
				x = x % y
		elif y % x == 0:
			y = x
		else:
			y = y % x
	print(x + y)
	t = t - 1


def g(a, b):
	if b == 0:
		return a
	else:
		return g(b, a % b)
for t in range(int(input())):
	c = 0
	(x, y) = map(int, input().split())
	if x == y:
		print(x + y)
	elif x == 0 or y == 0:
		print(x + y)
	else:
		print(2 * g(x, y))


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	(M, B) = map(int, input().split())
	g = gcd(M, B)
	print(2 * g)


from math import *
t = int(input())
for i in range(t):
	(m, b) = input().split()
	m = int(m)
	b = int(b)
	print(2 * gcd(m, b))


t = int(input())
for i in range(0, t):
	(x, y) = map(int, input().split())
	while x != y and y != 0 and (x != 0):
		if x < y:
			if y % x == 0:
				y = x
				break
			y -= y // x * x
		else:
			if x % y == 0:
				x = y
				break
			x -= x // y * y
	print(x + y)


import math
T = int(input())
for i in range(T):
	(M, B) = map(int, input().split())
	res = math.gcd(M, B)
	print(res * 2)


from math import *
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	a = int(a)
	b = int(b)
	print(2 * gcd(a, b))


import math as ma
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	print(2 * ma.gcd(x, y))


import math
n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	print(math.gcd(a, b) * 2)


def the_deadly_sin(x, y):
	while y:
		(x, y) = (y, x % y)
	return x * 2
for i in range(int(input())):
	(x, y) = map(int, input().split())
	print(the_deadly_sin(x, y))


import math
for i in range(int(input())):
	(n, m) = map(int, input().split())
	print(math.gcd(n, m) * 2)


t = int(input())
for _ in range(t):
	(a, b) = list(map(int, input().split()))
	while a != 0 and b != 0 and (a != b):
		if a > b:
			a = a % b
		else:
			b = b % a
	if a == 0 or b == 0:
		print((a + b) * 2)
	elif a == b:
		print(a + b)


t = int(input())
for i in range(t):
	(m, b) = list(map(int, input().split()))
	while m != b and m != 0 and (b != 0):
		if b == 1 or m == 1:
			m = 1
			b = 1
			break
		if m < b:
			if b % m == 0:
				b = m
				break
			b = b - b // m * m
		else:
			if m % b == 0:
				m = b
				break
			m = m - m // b * b
	print(m + b)


def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)
t = int(input())
while t != 0:
	arr = [int(i) for i in input().split()]
	x = arr[0]
	y = arr[1]
	print(2 * gcd(x, y))
	t -= 1


def gcd(x, y):
	if x == 0:
		return y
	return gcd(y % x, x)
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	print(2 * gcd(x, y))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	while a != b:
		if b > a:
			(a, b) = (b, a)
		if a % b == 0:
			a = b
		else:
			a = a % b
	print(a + b)


import math
n = int(input())
while n > 0:
	(a, b) = list(map(int, input().split()))
	x = 2 * math.gcd(a, b)
	print(x)
	n = n - 1


def gcd(a, b):
	if a > b:
		return gcd(b, a)
	elif a == 0:
		return b
	return gcd(b % a, a)
t = int(input())
while t:
	(x, y) = [int(i) for i in input().split()]
	if not x or not y:
		print(x + y)
	else:
		print(2 * gcd(x, y))
	t -= 1


def fun(M, B):
	if M == B:
		return M * 2
	elif M == 0:
		return B * 2
	elif B == 0:
		return M * 2
	elif M > B:
		return fun(M % B, B)
	else:
		return fun(M, B % M)
t = int(input())
for i in range(t):
	(M, B) = list(map(int, input().split()))
	print(fun(M, B))


import math
for _ in range(int(input())):
	(m, b) = map(int, input().split())
	print(math.gcd(m, b) * 2)


import math
n = int(input())
for i in range(n):
	l = list(map(int, input().split()))
	r = math.gcd(l[0], l[1])
	print(2 * r)


for _ in range(int(input())):
	[m, b] = [int(i) for i in input().split()]

	def E(m, b):
		if m < b:
			return E(b, m)
		if b == 0:
			return m
		return E(b, m % b)
	print(2 * E(m, b))


t = int(input())

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for _ in range(t):
	(x, y) = [int(a) for a in input().split()]
	print(gcd(x, y) * 2)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	if x > y:
		if x % y == 0:
			x = y
		else:
			x %= y
	elif y > x:
		if y % x == 0:
			y = x
		else:
			y %= x
	while x != y:
		if x > y:
			x -= y
		else:
			y -= x
	print(x + y)


from math import pow

def the_deadly_sin(x, y):
	while y:
		(x, y) = (y, x % y)
	return x * 2
from sys import setrecursionlimit
setrecursionlimit(int(pow(10, 9)))
for i in range(int(input())):
	(x, y) = map(int, input().split())
	print(the_deadly_sin(x, y))


def chocoValue(a, b):
	if a < b:
		(a, b) = (b, a)
	if b == 0:
		return a
	return chocoValue(b, a % b)
for x in range(int(input())):
	(m, b) = map(int, input().split())
	if m or b:
		sumValue = chocoValue(m, b)
		print(2 * sumValue)
	else:
		print(0)


for _ in range(int(input())):
	(x, y) = list(map(int, input().split()))
	while y:
		(x, y) = (y, x % y)
	print(2 * x)


from math import gcd
for i in range(int(input())):
	(a, s) = list(map(int, input().split()))
	print(gcd(a, s) * 2)


t = input()
for c in range(0, int(t)):
	(X, Y) = map(int, input().split())
	while X != Y:
		if Y > X:
			(Y, X) = (X, Y)
		if Y == 0:
			break
		if X % Y == 0:
			X = Y
		else:
			X %= Y
	print(X + Y)


def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	if b == 0:
		return a
	return gcd(b, a % b)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a or b:
		c = gcd(a, b)
		print(2 * c)
	else:
		print(0)


import math
T = int(input())
for _ in range(0, T):
	(x, y) = map(int, input().split())
	if x == 0 or y == 0:
		print(x + y)
	else:
		print(math.gcd(x, y) * 2)


def fun(m, n):
	if m == n or m == 0 or n == 0:
		return m + n
	elif m > n:
		if m % n == 0:
			return 2 * n
		else:
			return fun(m % n, n)
	elif n % m == 0:
		return 2 * m
	else:
		return fun(m, n % m)
t = int(input())
l = []
for i in range(t):
	(m, n) = tuple(map(int, input().split()))
	l.append(fun(m, n))
for i in range(t):
	print(l[i])


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	while True:
		if x == y or x == 0 or y == 0:
			break
		elif x > y:
			if x % y == 0:
				x = y
			else:
				x = x % y
		elif y % x == 0:
			y = x
		else:
			y = y % x
	print(x + y)


n = int(input())

def gcd(a, b):
	if b == 0:
		return a
	temp = a % b
	return gcd(b, temp)
for i in range(n):
	(a, b) = map(int, input().split())
	print(2 * gcd(a, b))


n = int(input())
for i in range(n):
	(x, y) = list(map(int, input().split()))
	while x != y or x == y == 0:
		if x > y:
			if x % y == 0:
				x = y
			else:
				x = x % y
		elif y % x == 0:
			y = x
		else:
			y = y % x
	print(x + y)


import math
for _ in range(int(input())):
	(X, Y) = map(int, input().split())
	print(max(X, Y) if X * Y == 0 else math.gcd(X, Y) * 2)


from math import gcd
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a and b and (a != b):
		(a, b) = (gcd(a, b), gcd(a, b))
	print(a + b)


import math
x = int(input())
for i in range(x):
	(a, b) = map(int, input().split())
	if math.gcd(a, b) == 1:
		print('2')
	else:
		print(math.gcd(a, b) * 2)


import math as ma
t = int(input())
while t:
	(m, b) = list(map(int, input().split()))
	print(2 * ma.gcd(m, b))
	t -= 1


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def choc(m, b):
	if m == b:
		return m + b
	elif m > b:
		x = gcd(m, b)
		return 2 * x
	elif b > m:
		x = gcd(b, m)
		return 2 * x
t = int(input())
mc = []
bc = []
for i in range(t):
	(a, b) = map(int, input().split())
	mc.append(a)
	bc.append(b)
for i in range(t):
	print(choc(mc[i], bc[i]))