Read problems statements in Mandarin Chinese  and Russian. 

Tuzik is a little dog. But despite the fact he is still a puppy he already knows about the pretty things that coins are. He knows that for every coin he can get very tasty bone from his master. He believes that some day he will find a treasure and have loads of bones.

And finally he found something interesting. A wooden chest containing N coins! But as you should remember, Tuzik is just a little dog, and so he can't open it by himself. Actually, the only thing he can really do is barking. He can use his barking to attract nearby people and seek their help. He can set the loudness of his barking very precisely, and therefore you can assume that he can choose to call any number of people, from a minimum of 1, to a maximum of K.

When people come and open the chest they divide all the coins between them in such a way that everyone will get the same amount of coins and this amount is maximal possible. If some coins are not used they will leave it on the ground and Tuzik will take them after they go away. Since Tuzik is clearly not a fool, he understands that his profit depends on the number of people he will call. While Tuzik works on his barking, you have to find the maximum possible number of coins he can get.

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

The first line of the input contains an integer T denoting the number of test cases. Each of next T lines contains 2 space-separated integers: N and K, for this test case.

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

For each test case output one integer - the maximum possible number of coins Tuzik can get.

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

$1 ≤ T ≤ 50$
$1 ≤ N, K ≤ 10^{5}$

----- Sample Input 1 ------ 
2

5 2

11 3
----- Sample Output 1 ------ 
1

2
----- explanation 1 ------ 
In the first example he should call two people. Each of them will take 2 coins and they will leave 1 coin for Tuzik.
In the second example he should call 3 people.

Difficulty: EASY
Tags: Mathematics

Implementation

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k) = tuple(map(int, input().split()))
	res = 0
	for num in range(1, k + 1):
		if n % num > res:
			res = n % num
	print(res)


for h in range(int(input())):
	(n, k) = map(int, input().split())
	maxi = 0
	for i in range(1, k + 1):
		maxi = max(maxi, n % i)
	print(maxi)


test_num = int(input())
for k in range(0, test_num):
	(str_N, str_K) = input().split()
	N = int(str_N)
	K = int(str_K)
	max = 0
	for k in range(1, K + 1):
		cur = N % k
		if cur > max:
			max = cur
	print(max)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = []
	for i in range(1, k + 1):
		tuzik_get = n % i
		arr.append(tuzik_get)
	print(max(arr))


t = int(input())
for i in range(0, t):
	(n, k) = map(int, input().split())
	li = []
	for j in range(1, k + 1):
		li.append(n % j)
	print(max(li))


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	r = 0
	for j in range(1, k + 1):
		s = n % j
		if s >= r:
			r = s
	print(r)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = []
	for i in range(1, k + 1):
		l.append(n % i)
	print(max(l))


for t in range(int(input())):
	(n, k) = map(int, input().split())
	call = 0
	for i in range(1, k + 1):
		call = max(call, n % i)
	print(call)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	highest = 1
	while k > highest:
		temp = n % k
		if temp > highest:
			highest = temp
		k -= 1
	print(highest)


t = int(input())
f = []
for nn in range(0, t):
	h = str(input())
	m = h.split(' ')
	gv = []
	for nnt in m:
		gv.append(int(nnt))
	f.append(gv)
for nn in f:
	lt = 0
	for jjk in range(2, nn[1] + 1):
		gcx = nn[0] // jjk * jjk
		bty = nn[0] - gcx
		if bty > lt:
			lt = bty
	print(lt)


for _ in range(int(input())):
	(a, b) = list(map(int, input().split()))
	k = 0
	for i in range(1, b + 1):
		if k < a % i:
			k = a % i
	print(k)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	j = []
	for i in range(1, k + 1):
		j.append(n % i)
	print(max(j))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	mp = 0
	for i in range(1, k + 1):
		if n % i > mp:
			mp = n % i
	print(mp)


t = int(input())
for i in range(t):
	(m, n) = map(int, input().split())
	a = 0
	for j in range(1, n + 1):
		x = m % j
		if x > a:
			a = x
	print(a)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	z = 0
	for i in range(1, y + 1):
		z = max(z, x % i)
	print(z)


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	ax = 0
	for i in range(1, k + 1):
		ay = n % i
		if ay > ax:
			ax = ay
	print(ax)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	z = x % y
	while y != 1:
		y = y - 1
		if z < x % y:
			z = x % y
	print(z)


n = int(input())
for i in range(0, n):
	a = [int(x) for x in input().split()]
	(x, y) = (a[0], a[1])
	d = 0
	for j in range(1, y + 1):
		if x % j > d:
			d = x % j
	print(d)


tc = int(input())
for _ in range(tc):
	(n, k) = [int(x) for x in input().split()]
	max = 0
	for i in range(2, k + 1):
		remainder = n % i
		if remainder > max:
			max = remainder
	print(max)


n = int(input())
for i in range(n):
	(x, y) = map(int, input().split())
	t = 0
	for i in range(1, y + 1):
		t = max(t, x % i)
	print(t)


for i in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	A = []
	for j in range(1, k + 1):
		A.append(n % j)
	print(max(A))


for i in range(int(input())):
	(a, b) = [int(i) for i in input().split()]
	t = 0
	for i in range(1, b + 1):
		t = max(t, a % i)
	print(t)


for _ in range(int(input())):
	(x, y) = list(map(int, input().split()))
	k = 0
	for i in range(1, y + 1):
		if k < x % i:
			k = x % i
	print(k)


t = int(input())
res = []
for _ in range(t):
	(n, k) = map(int, input().split())
	max = 0
	for i in range(1, k + 1):
		if n % i > max:
			max = n % i
	res.append(max)
	pass
print(*res, sep='\n')


try:
	for _ in range(int(input())):
		(N, K) = map(int, input().split())
		L = []
		for i in range(1, K + 1):
			L.append(N % i)
		print(max(L))
except:
	pass


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	maxi = 0
	for i in range(1, k + 1):
		m = n % i
		maxi = max(maxi, m)
	print(maxi)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	maxi = 0
	for j in range(1, k + 1):
		each = n // j
		rem = n - each * j
		if rem > maxi:
			maxi = rem
	print(maxi)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	tuzik = 0
	for i in range(1, K + 1):
		tuzik = max(tuzik, N % i)
	print(tuzik)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	x = -1
	for i in range(1, b + 1):
		x = max(x, a % i)
	print(x)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	maxi = 0
	for _ in range(1, k + 1):
		if n % _ > maxi:
			maxi = n % _
	print(maxi)


for tc in range(int(input())):
	(n, k) = map(int, input().split())
	ans = []
	for i in range(1, k + 1):
		ans.append(n % i)
	print(max(ans))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	max = 0
	for i in range(1, k + 1):
		if n % i > max:
			max = n % i
	print(max)


p = int(input())
for k in range(p):
	(a, b) = map(int, input().split())
	d = 0
	for l in range(1, b + 1):
		d = max(d, a % l)
	print(d)


t = int(input())
while t != 0:
	(c, p) = map(int, input().split())
	r = 0
	for k in range(1, p + 1):
		if c % k > r:
			r = c % k
	print(r)
	t -= 1


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	m = n % k
	while k != 1:
		k -= 1
		if m < n % k:
			m = n % k
	print(m)


for tc in range(int(input())):
	(n, k) = map(int, input().split())
	(rem, maxrem) = (0, 0)
	for i in range(1, k + 1):
		rem = n % i
		if rem > maxrem:
			maxrem = rem
	print(maxrem)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = a % b
	while b != 1:
		b = b - 1
		if c < a % b:
			c = a % b
	print(c)


T = int(input())
for i in range(T):
	(N, K) = [int(x) for x in input().split()]
	a = []
	for i in range(1, K + 1):
		a.append(N % i)
	print(max(a))


a = int(input(''))
for i in range(a):
	(X, Y) = [int(x) for x in input('').split()]
	l = []
	for j in range(1, Y + 1):
		t = X % j
		l.append(t)
	print(max(l))


inp = int(input())
for i in range(inp):
	(n, k) = map(int, input().split())
	a = []
	for j in range(1, k + 1):
		a.append(n % j)
	print(max(a))


for i in range(int(input())):
	(a, b) = map(int, input().split())
	l = []
	for i in range(1, b + 1):
		l.append(a % i)
	print(max(l))


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	a = []
	for i in range(1, k + 1):
		a.append(n % i)
	print(max(a))


import math
for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = []
	for j in range(1, k + 1):
		l.append(n % j)
	print(max(l))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	for i in range(1, k + 1):
		ans = max(ans, n % i)
	print(ans)


try:
	t = int(input())
	for i in range(t):
		l = []
		(n, k) = map(int, input().split(' '))
		for i in range(1, k + 1):
			l.append(n % i)
		print(max(l))
except:
	pass


n = int(input())
for i in range(n):
	(x, y) = map(int, input().split())
	c = 0
	for j in range(1, y + 1):
		c = max(c, x % j)
	print(c)


x = input()
t = int(x)
for i in range(0, t):
	(n, k) = input().split()
	i1 = int(n)
	i2 = int(k)
	max = i1 % 1
	for j in range(2, i2 + 1):
		r = i1 % j
		if r > max:
			max = r
	print(max)


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	maxi = 0
	for i in range(1, K + 1):
		r = N % i
		if r >= maxi:
			maxi = r
	print(maxi)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	mx = 0
	for i in range(2, K + 1):
		t = N % i
		mx = max(mx, t)
	print(mx)


def puppy(n, k):
	maxx = 0
	for i in range(1, k + 1):
		if n % i > maxx:
			maxx = n % i
	return maxx
for i in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	print(puppy(n, k))


for _ in range(int(input())):
	(V, J) = map(int, input().split())
	tuzik = 0
	for i in range(1, J + 1):
		tuzik = max(tuzik, V % i)
	print(tuzik)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	cur = n % k
	for i in range(k, 1, -1):
		if i <= cur:
			break
		c = n % i
		if c > cur:
			cur = c
	print(cur)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	highest = 1
	while k > highest:
		temp = n % k
		if temp > highest:
			highest = temp
		k -= 1
	print(highest)


t = int(input())
for i in range(t):
	(N, K) = list(map(int, input().split()))
	maxi = N % K
	for i in range(1, K):
		if N % i > maxi:
			maxi = N % i
	print(maxi)


t = int(input())
for i in range(t):
	(N, K) = list(map(int, input().split()))
	bar = 0
	for j in range(1, K + 1):
		if N % j > bar:
			bar = N % j
	print(bar)


test = int(input())
while test is not 0:
	(a, b) = map(int, input().split())
	c = []
	for _ in range(1, b + 1):
		c.append(a % _)
	print(max(c))
	test -= 1


T = int(input())
x = range(T)
for i in x:
	(a, b) = map(int, input().split())
	c = 0
	for j in range(1, b + 1):
		if c < a % j:
			c = a % j
	print(c)


import sys

def main():
	for _ in range(int(sys.stdin.readline())):
		(n, k) = map(int, sys.stdin.readline().split())
		print(max([n % j for j in range(1, k + 1)]))
main()


t = int(input())
while t != 0:
	t = t - 1
	(n, k) = map(int, input().split())
	m = 0
	for i in range(1, k + 1):
		ans = n % i
		m = max(m, ans)
	print(m)


for _ in range(int(input())):
	a = list(map(int, input().split()))
	(r, m) = (0, 1)
	for i in range(1, a[1] + 1):
		r = max(r, a[0] % i)
	print(r)