A seminar of Artificial Intelligence is going on,and the number of participants from Foreign is N, while from India is M. All the participants would be staying in the same hotel.In each room equal number of participants have to stay( can be 1 in a room).Also foreign and Indian cannot stay in the same room. Find the minimum number of rooms required,if in each room the same number of participants are to be seated.
Example 1:
Input: N = 60, M = 84
Output: 12
Explaination: In each room we will keep 12 
person. So total 5+7 = 12 rooms are required.
Example 2:
Input: N = 8, M = 11
Output: 19
Explaination: We can keep 1 person in each 
room. So total 19 rooms are required.
Your Task:
You do not need to read input or print anything. Your task is to complete the function rooms() which takes N and M as input parameters and returns minimum required rooms.
Expected Time Complexity: O(log(max(N,M)))
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N, M ≤ 1000

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3

class Solution:
    def rooms(self, N, M):
        # code here

Solutions:
class Solution:

	def rooms(self, N, M):

		def hcf(a, b):
			if b == 0:
				return a
			else:
				return hcf(b, a % b)
		h = hcf(N, M)
		return N // h + M // h


class Solution:

	def gcd(self, a, b):
		r = a % b
		while r > 0:
			a = b
			b = r
			r = a % b
		return b

	def rooms(self, N, M):
		t = self.gcd(max(N, M), min(N, M))
		return N // t + M // t


class Solution:

	def gcd(self, a, b):
		ans = 1
		for i in range(min(a, b), 0, -1):
			if a % i == 0 and b % i == 0:
				ans = i
				break
		return ans

	def rooms(self, N, M):
		k = self.gcd(N, M)
		l = N // k + M // k
		return l


import math

class Solution:

	def rooms(self, N, M):
		p = math.gcd(N, M)
		return N // p + M // p


import math

class Solution:

	def rooms(self, N, M):
		greatest_common_divisor = math.gcd(N, M)
		min_room_required = N / greatest_common_divisor + M / greatest_common_divisor
		return int(min_room_required)


class Solution:

	def rooms(self, N, M):
		a = N + M
		for i in range(1, max(N, M) + 1):
			if N % i == 0 and M % i == 0:
				a = min(a, int(N / i) + int(M / i))
		return a


import math

class Solution:

	def rooms(self, N, M):
		c = math.gcd(N, M)
		room = N // c + M // c
		return room


class Solution:

	def eular(self, a, b):
		if a == 0:
			return b
		return self.eular(b % a, a)

	def rooms(self, N, M):
		ans = self.eular(N, M)
		return N // ans + M // ans


import math

class Solution:

	def rooms(self, n, m):
		h = math.gcd(n, m)
		return n // h + m // h


class Solution:

	def rooms(self, N, M):
		gcd = self.gcd(N, M)
		return N // gcd + M // gcd

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


class Solution:

	def rooms(self, N, M):

		def hcf(x, y):
			while y:
				(x, y) = (y, x % y)
			return x
		return (N + M) // hcf(N, M)


class Solution:

	def rooms(self, N, M):
		gcd = 1
		backup_M = M
		backup_N = N
		while 1:
			if N == 0:
				gcd = M
				break
			if M == 0:
				gcd = N
				break
			elif M > N:
				M = M % N
			else:
				N = N % M
		backup_M = int(backup_M / gcd)
		backup_N = int(backup_N / gcd)
		return backup_M + backup_N


import math

class Solution:

	def rooms(self, N, M):
		x = math.gcd(N, M)
		return N // x + M // x


class Solution:

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

	def rooms(self, N, M):
		part = self.gcd(min(N, M), max(M, N))
		return (N + M) // part
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M) = [int(x) for x in input().split()]
		ob = Solution()
		print(ob.rooms(N, M))


from math import gcd

class Solution:

	def rooms(self, N, M):
		return (N + M) // gcd(M, N)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M) = [int(x) for x in input().split()]
		ob = Solution()
		print(ob.rooms(N, M))


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

class Solution:

	def rooms(self, N, M):
		g = gcd(N, M)
		res = N // g + M // g
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M) = [int(x) for x in input().split()]
		ob = Solution()
		print(ob.rooms(N, M))


class Solution:

	def rooms(self, a, b):
		i = 1
		while i <= a and i <= b:
			if a % i == 0 and b % i == 0:
				val = i
			i = i + 1
			ans = a // val + b // val
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M) = [int(x) for x in input().split()]
		ob = Solution()
		print(ob.rooms(N, M))


class Solution:

	def rooms(self, N, M):
		return int((N + M) / self.gcd(N, M))

	def gcd(self, a, b):
		if a == 0:
			return b
		g = self.gcd(b % a, a)
		return g


from math import gcd

class Solution:

	def rooms(self, N, M):
		d = gcd(N, M)
		return int(N / d + M / d)


class Solution:

	def gcd(self, n, m):
		if n == 0:
			return m
		return self.gcd(m % n, n)

	def rooms(self, N, M):
		return (N + M) // self.gcd(min(N, M), max(N, M))


class Solution:

	def gcd(self, N, M):
		if N == 0:
			return M
		return self.gcd(M % N, N)

	def rooms(self, N, M):
		seats_in_room = self.gcd(N, M)
		return int((N + M) / seats_in_room)


class Solution:

	def rooms(self, N, M):

		def gcd(n, m):
			if n == 0:
				return m
			return gcd(m % n, n)
		g = gcd(N, M)
		return (N + M) // g


class Solution:

	def rooms(self, N, M):
		return main(N, M)

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

def main(N, M):
	x = gcd(N, M)
	y = N // x + M // x
	return y


import math

class Solution:

	def rooms(self, N, M):
		if math.gcd(N, M) == 1:
			return N + M
		else:
			x = math.gcd(N, M)
			ans = N // x + M // x
			return ans


class Solution:

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

	def rooms(self, N, M):
		g = self.gcd(N, M)
		ans = N + M
		if g > 1:
			ans = ans // g
		return ans


class Solution:

	def gcd(self, x, y):
		if y == 0:
			return x
		return self.gcd(y, x % y)

	def rooms(self, N, M):
		g = self.gcd(N, M)
		if g == 1:
			return N + M
		return N // g + M // g


class Solution:

	def rooms(self, N, M):

		def gcd(n1, n2):
			if n1 > n2:
				(n1, n2) = (n2, n1)
			if n1 == 0:
				return n2
			return gcd(n2 % n1, n1)
		x = gcd(N, M)
		return N // x + M // x


class Solution:

	def rooms(self, N, M):

		def gcd_(a, b):
			while b:
				(a, b) = (b, a % b)
			return a
		x = gcd_(N, M)
		return N // x + M // x


class Solution:

	def rooms(self, N, M):

		def gcd(a, b):
			if b == 0:
				return a
			return gcd(b, a % b)
		gc = gcd(N, M)
		room = N // gc + M // gc
		return room


class Solution:

	def gcd(self, n, m):
		if m > n:
			return self.gcd(m, n)
		if m == 0:
			return n
		return self.gcd(m, n % m)

	def rooms(self, n, m):
		b = self.gcd(m, n % m)
		return round(n / b + m / b)


class Solution:

	def rooms(self, N, M):
		div = N
		divd = M
		rem = 1
		while rem != 0:
			rem = divd % div
			divd = div
			div = rem
		x = N / divd
		y = M / divd
		return int(x + y)


class Solution:

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

	def rooms(self, n, m):
		gcd = self.gcd(n, m)
		return int((n + m) / gcd)


class Solution:

	def rooms(self, N, M):
		peopleCount = 0
		smaller = 0
		if N > M:
			smaller = M
		else:
			smaller = N
		for x in range(smaller, 0, -1):
			if N % x == 0 and M % x == 0:
				peopleCount = x
				break
		return int(N / peopleCount + M / peopleCount)