Chef is throwing a party for his N friends. There is a pizza store nearby and he wants to buy pizza for his friends. Each pizza has exactly K slices. Chef's friends get sad if one gets more slices than the other. Also, Chef gets sad if there are some pizza slices left. More formally, suppose Chef buys P pizzas, then everyone is happy if and only if there is a way to distribute K \cdot P slices between N friends.

You need to find the minimum number of pizzas Chef has to buy to share all the slices among his friends so that none of his friends gets sad. Note that Chef hates pizza and doesn't take any slices.

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

- First line of input contains T, the number of test cases. Then the test cases follow.
- Each test case contains two space-separated integers N and K, where N is the number of friends of chef and K is the number of slices in a pizza.

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

For each test case, print the minimum number of pizzas chef has to buy to share among his friends so that none of his friends gets sad.

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

$1 ≤ T ≤ 2 \cdot 10^{5}$
$1 ≤ N, K ≤ 10^{9}$

------ subtasks ------ 

Subtask 1 (100 points): Original constraints

----- Sample Input 1 ------ 
3
2 2
2 3
4 2

----- Sample Output 1 ------ 
1
2
2

----- explanation 1 ------ 
- Test case $1$: One pizza has $2$ slices. And there are $2$ friends. So chef can just buy one pizza and give one slice to one friend and another slice to another friend.
- Test case $2$: One pizza has $3$ slices. And there are $2$ friends. So chef can't share one pizza without being left out with a slice. So he needs to buy at least $2$ pizzas. And if he buys $2$ pizzas, he can give $3$ slices to one friend and $3$ to another. So the minimum number of pizzas chef needs to buy is equal to $2$.
- Test case $3$: One pizza has $2$ slices. And there are $4$ friends. So chef can't share one pizza among the $4$ friends. So he needs to buy at least $2$ pizzas. And if he buys $2$ pizzas, he can give $1$ slice to each of his friends. So the minimum number of pizzas chef needs to buy is equal to $2$.

Difficulty: MEDIUM
Tags: Number theory

Constructive algorithms

Mathematics

Ad-hoc

Starter code:

Solutions:
def hcf(a, b):
	if b == 0:
		return a
	else:
		return hcf(b, a % b)
for z in range(int(input())):
	(n, m) = map(int, input().split())
	s = n * m / hcf(n, m)
	s = round(s / m)
	print(s)


def hcf(a, b):
	if b == 0:
		return a
	else:
		return hcf(b, a % b)
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	Sol = N * K / hcf(N, K)
	Sol = Sol / K
	Sol = round(Sol)
	print(Sol)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	mul = n * k
	gd = gcd(n, k)
	lcm = mul // gd
	print(int(lcm / k))


import math as m
for i in range(int(input())):
	(n, k) = map(int, input().split())
	d = m.gcd(n, k)
	print(n // d)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	g = gcd(n, k)
	l = n * k // g
	ans = l // k
	print(ans)
	t -= 1


import math

def GCD(n, m):
	if m == 0:
		return n
	return GCD(m, n % m)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	gcd = GCD(n, k)
	lcm = n * k // gcd
	print(math.ceil(lcm / k))


def gcd(n, p):
	if n > p:
		(n, p) = (p, n)
	while p % n != 0:
		temp = p - n
		p = n
		n = temp
		if n > p:
			(n, p) = (p, n)
	return n
t = int(input())
for _ in range(t):
	(n, p) = map(int, input().split())
	print(n // gcd(n, p))


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(n // math.gcd(n, k))


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	ans = n * k // gcd(n, k)
	print(ans // k)


def calculate_pizzas(a, b):
	if b == 0:
		return a
	return calculate_pizzas(b, a % b)
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	print(n // calculate_pizzas(n, k))


def calculate_pizzas(a, b):
	x = max(a, b)
	y = min(a, b)
	while y != 0:
		(x, y) = (y, x % y)
	return x
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	print(n // calculate_pizzas(n, k))


def compute_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def compute_lcm(x, y):
	lcm = x * y // compute_gcd(x, y)
	return lcm
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	l = compute_lcm(n, k)
	print(int(l / k))


import math
t = int(input())
while t != 0:
	(f, s) = map(int, input().split())
	g = math.gcd(f, s)
	print(f // g)
	t -= 1


def compute_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def compute_lcm(x, y):
	lcm = x * y // compute_gcd(x, y)
	return lcm
T = int(input())
for t in range(T):
	(N, K) = list(map(int, input().split()))
	ans = compute_lcm(N, K) // K
	print(ans)


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

def calc_lcm(x, y):
	lcm = x * y // calc_gcd(x, y)
	return lcm
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	ans = calc_lcm(n, k) // k
	print(ans)


from math import gcd
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(n // gcd(n, m))


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


from math import gcd
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	print(n // gcd(n, k))


import math
for i in range(int(input())):
	(N, K) = map(int, input().split())
	HCF = math.gcd(N, K)
	print(int(N / HCF))


import numpy as np
tests = int(input())
for i in range(tests):
	(n, k) = map(int, input().split())
	LCM = np.lcm(n, k)
	print(LCM // k)


import math
tests = int(input())
for i in range(tests):
	(n, k) = map(int, input().split())
	lcm = n * k // math.gcd(n, k)
	print(lcm // k)


def gcd(n, k):
	if k > n:
		(n, k) = (k, n)
	if k == 0:
		return n
	return gcd(k, n % k)
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = n // gcd(n, k)
	print(l)


import math

def lcm(n, k):
	return n * k // math.gcd(n, k)
for i in range(int(input())):
	(n, k) = map(int, input().split())
	print(lcm(n, k) // k)


def gdc(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def lcm(x, y):
	lcm = x * y // gdc(x, y)
	return lcm
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n == k:
		print(1)
	elif n < k and k % n == 0:
		print(1)
	elif n > k and n % k == 0:
		print(n // k)
	else:
		ans = lcm(n, k) // k
		print(ans)


from math import gcd
a = int(input())
for i in range(0, a):
	(x, y) = [int(i) for i in input().split()]
	if x == y:
		print(1)
	else:
		print(x * y // gcd(x, y) // y)


def euclidgcd(a, b):
	if a < b:
		return euclidgcd(b, a)
	elif b == 0:
		return a
	else:
		return euclidgcd(b, a % b)
for i in range(int(input())):
	(N, K) = map(int, input().split())
	ans = euclidgcd(N, K)
	LCM = N * K // ans
	LCM = LCM // K
	print(LCM)


import math
T = int(input())
friend = []
piece = []
for i in range(0, T):
	(N, K) = input().split()
	N1 = int(N)
	friend.append(N1)
	K1 = int(K)
	piece.append(K1)
for i in range(0, T):
	print(int(friend[i] / math.gcd(friend[i], piece[i])))


import math
cases = int(input())
for i in range(0, cases):
	(friend, slices) = [int(x) for x in input().split()]
	order = int(friend / math.gcd(friend, slices))
	print(order)


from bisect import bisect_left, bisect_right
import math
from bisect import bisect_left
from heapq import heapify, heappush, heappop
from collections import deque
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
from collections import deque, defaultdict
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

def ip():
	return input().strip()

def ii():
	return int(input())

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for i in range(ii()):
	(n, k) = il()
	a = math.gcd(n, k)
	print(n // a)


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if gcd(n, k) == 1:
		print(n)
	else:
		print(n // gcd(n, k))


from math import gcd, sqrt, ceil, floor, log10, log2
from heapq import heapify, heappop, heappush, nsmallest, nlargest
from collections import Counter, deque, OrderedDict, defaultdict
from itertools import combinations, permutations, zip_longest
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
import sys
import time
import string
import operator
RECURSION_LIMIT = int(10000000.0)
INT_MAX = float('inf')
INT_MIN = float('-inf')
MOD = int(1000000000.0) + 7
NEWLINE = '\n'
SPACE = ' '
sys.setrecursionlimit(RECURSION_LIMIT)
inp = lambda fn: fn(input())
inp_vars = lambda fn, delim, convert_to=list: convert_to(map(fn, input().split(delim)))

def inp_graph(n, adj, gtype=0):
	pass

def solve(*args, **kwargs):
	(n, k) = args[0]
	lcm = n * k // gcd(n, k)
	return lcm // k

def main(*args, **kwargs):
	for _ in range(int(input())):
		arg2 = inp_vars(int, SPACE)
		res = solve(*(arg2,))
		if type(res) in {list, tuple, set}:
			print(*res, sep=' ')
		else:
			print(res)
main()


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

def party(n, k):
	hcf = gcd(n, k)
	lcm = n * k // hcf
	return lcm // k
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	print(party(n, k))


import math
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	j = n // math.gcd(n, k)
	print(j)


import math

def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		print(n // math.gcd(n, k))
main()


import math
from sys import stdin
for _ in range(int(stdin.readline())):
	(n, k) = [int(a) for a in stdin.readline().split()]
	print(int(n // math.gcd(n, k)))


import math
for _ in range(int(input())):
	(n, k) = [int(a) for a in input().split()]
	print(int(n // math.gcd(n, k)))