Given two matrices A and B. Both have N rows and M columns. In the matrix A, numbers from 1 to MN have been written in row major order. Row major order numbers cells from left to right, and top to bottom. That is,

1                  2                 3             ...     M
A  =    M+1             M+2            M+3        ...     2M
2M+1           2M+2          2M+3       ...   3M
.                   .                  .              ...      .
.                   .                  .               ...      .
(N-1)M+1    (N-1)M+2    (N-1)M+3   ...   NM

Similarly, in the matrix B, numbers from 1 to MN have been written in column major order. Column major order numbers cells from top to bottom and left to right.

You are to count number of pairs (i,j) such that A_{i,j}=B_{i,j}.

------ Input ------ 

The input consists of multiple test cases. The first line of input contains a single integer T, the number of test cases. T test cases follow. Each test case is described by one line containing two space separated integers, N and M

------ Output ------ 

Output T lines, i^{th} line containing answer of the i^{th} test case.

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

1 ≤ T ≤ 10^{5} 1 ≤ N, M ≤ 10^{9}

----- Sample Input 1 ------ 
1
4 5
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
For the first case two matrices look as follows:
A=
1 2 3 4 5 
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20B=
1 5 9 13 17
2 6 10 14 18
3 7 11 15 19
4 8 12 16 20
A1,1=B1,1A4,5=B4,5

Difficulty: MEDIUM_HARD
Tags: Mathematics

Starter code:

Solutions:
import fractions
T = int(input())
for t in range(T):
	(N, M) = map(int, input().split())
	print(fractions.gcd(N - 1, M - 1) + 1)


import fractions

def main():
	tc = int(input())
	for i in range(tc):
		nm = input().split(' ')
		n = int(nm[0])
		m = int(nm[1])
		if n == m:
			print(n)
		elif n == 1 or m == 1:
			print(m * n)
		else:
			print(fractions.gcd(n - 1, m - 1) + 1)
main()


def gcd(a, b):
	while True:
		if a == 0:
			return b
		else:
			b %= a
		if b == 0:
			return a
		else:
			a %= b
t = int(input())
for it in range(t):
	(n, m) = [int(word) for word in input().split()]
	g = gcd(m - 1, n - 1)
	print(g + 1)


import math
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(math.gcd(n - 1, m - 1) + 1)


def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	while b != 0:
		r = b
		b = a % r
		a = r
	return a
t = int(input())
for z in range(t):
	(n, m) = map(int, input().split())
	if n == 1 or m == 1:
		print(max(n, m))
	else:
		value = gcd(n - 1, m - 1)
		print(value + 1)


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


__author__ = 'star-lord'
from fractions import gcd
testCase = int(input())
while testCase > 0:
	(n, m) = map(int, input().strip().split())
	if n == 1 or m == 1:
		print(max(m, n))
	else:
		print(gcd(m - 1, n - 1) + 1)
	testCase -= 1


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


def main():
	import sys

	def GCD(a, b):
		if b == 0:
			return a
		elif a == 0:
			return b
		elif a % 2 == b % 2 == 0:
			return 2 * GCD(a // 2, b // 2)
		elif a % 2 == 0:
			return GCD(a // 2, b)
		elif b % 2 == 0:
			return GCD(a, b // 2)
		elif a > b:
			return GCD(a % b, b)
		else:
			return GCD(b % a, a)
	input()
	for inp in sys.stdin:
		(N, M) = map(int, inp.split())
		if N == 1 or M == 1:
			print(max(N, M))
		else:
			print(GCD(N - 1, M - 1) + 1)
main()


__author__ = 'star-lord'

def gcd(a, b):
	if a == 0:
		return b
	if b == 0:
		return a
	return gcd(b, a % b)
testCase = int(input())
while testCase > 0:
	(n, m) = map(int, input().strip().split())
	if n == 1 or m == 1:
		print(max(m, n))
	else:
		print(gcd(m - 1, n - 1) + 1)
	testCase -= 1


import math
t = int(input())
while t > 0:
	(x, y) = map(int, input().split())
	if x == 1 or y == 1:
		print(x * y)
	else:
		print(math.gcd(x - 1, y - 1) + 1)
	t = t - 1


def main():
	import sys
	from fractions import gcd
	input()
	for inp in sys.stdin:
		(N, M) = map(int, inp.split())
		if N == 1 or M == 1:
			print(max(N, M))
		else:
			print(gcd(N - 1, M - 1) + 1)
main()


import fractions
T = int(input())
if not 1 <= T <= 10 ** 5:
	print('wrong input')
for t in range(T):
	(N, M) = map(int, input().split())
	if not 1 <= N <= 10 ** 9 and 1 <= M <= 10 ** 9:
		print('wrong input')
	print(fractions.gcd(N - 1, M - 1) + 1)