Chef wants you to distribute candies among $N$ kids who are sitting in a circle. However, he wants to make some kids jealous of others. Thus, he wants you to distribute candies in such a way that there is a difference of at least $K$ candies between two adjacent kids. 
Given the value of $N$ and $K$, you need to find the minimum number of candies you need to satisfy the given conditions, such that, each kid gets at least one candy.

-----Input:-----
- First line will contain $T$, the number of testcases. Then the testcases follow. 
- The only line of each testcase contains two space-separated integers $N$ and $K$. 

-----Output:-----
For each test case, print a single line containing one integer ― the number of candies you need.

-----Constraints-----
- $1 \leq T \leq  10^6$
- $2 \leq  N \leq  10^3$
- $0 \leq  K \leq 10^4$ 

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

-----Sample Output:-----
3

-----EXPLANATION:-----
The minimum number of candies required is $3$. One kid needs to have $1$ candy and the other needs to have $2$ candy to have a difference of $1$ candy between them.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
for _ in range(int(input())):
	(n, k) = [int(v) for v in input().split()]
	ans = n // 2 * (k + 2)
	if n % 2 == 0:
		ans = ans
	else:
		ans += 1 + 2 * k
	print(ans)


t = int(input())
l = []
for i in range(t):
	(n, k) = map(int, input().split())
	can = 0
	if n % 2 == 0:
		can = n // 2 + (n - n // 2) * (k + 1)
	else:
		can = n // 2 + 1 + (n - n // 2 - 1) * (k + 1) + 2 * k
	l.append(can)
for x in range(t):
	print(l[x])


t = int(input())
for i in range(t):
	(m, l) = list(map(int, input().split()))
	if m == 1:
		print(1)
	else:
		s = (2 + l) * (m // 2)
		if m % 2 != 0:
			s += 1 + 2 * l
		print(s)


t = int(input())
r = []
for each in range(t):
	(n, k) = list(map(int, input().split()))
	if n % 2 == 0:
		r.append(n + n * k // 2)
	else:
		n = n - 1
		r.append(n + n * k // 2 + 1 + 2 * k)
for each in r:
	print(each)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	if n == 1:
		print(1)
	else:
		r = (2 + k) * (n // 2)
		if n % 2 != 0:
			r += 1 + 2 * k
		print(r)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(n // 2 * (k + 2) + n % 2 * (2 * k + 1))


t = int(input())
while t != 0:
	(n, k) = list(map(int, input().split()))
	if n % 2 == 0:
		even = n / 2
		odd = n / 2 * (k + 1)
	else:
		odd = (n - 1) / 2 * (k + 1)
		even = (n - 1) / 2 + (1 + 2 * k)
	total = even + odd
	print(int(total))
	t -= 1


for i in range(int(input())):
	(n, k) = map(int, input().split())
	if k == 0:
		print(n)
	elif n % 2 == 0:
		s = n // 2 + n // 2 * (k + 1)
		print(s)
	else:
		s = n // 2 + 2 * (k + 1) + n // 2 * (k + 1)
		print(s - 1)


t = int(input())
for z in range(t):
	(n, k) = list(map(int, input().split()))
	if n % 2 == 0:
		print(n + k * n // 2)
	else:
		print(n + ((n - 1) // 2 + 2) * k)


t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	ans = n // 2 * (k + 2) + n % 2 * (2 * k + 1)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n % 2 == 0:
		print(n + n // 2 * k)
	elif n == 3:
		print(n + 3 * k)
	else:
		print(n + 3 * k + (n - 3) // 2 * k)


from sys import stdin
try:
	for _ in range(int(stdin.readline())):
		(n, k) = map(int, stdin.readline().rstrip().split())
		if n % 2 == 0:
			candy = (k + 2) * n // 2
		elif n == 3:
			candy = 3 + 3 * k
		else:
			candy = (k + 2) * (n - 1) // 2 + (2 * k + 1)
		print(candy)
except:
	pass


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = 0
	if n % 2 == 0:
		s = int(n / 2 * (k + 2))
	else:
		s = int((n - 1) / 2 * (k + 2)) + (2 * k + 1)
	print(s)


t = int(input())
l = []
while t:
	q = input()
	l = q.split()
	n = int(l[0])
	k = int(l[1])
	if n % 2 == 0:
		print(int(n / 2 + n / 2 * (1 + k)))
	else:
		print(int(n // 2 + n // 2 * (1 + k) + 1 + 2 * k))
	t = t - 1


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	if n % 2 == 0:
		print(k * (n // 2) + n)
	if n % 2 == 1:
		print(k * (n // 2) + 2 * k + n)


n = int(input())
for i in range(n):
	ans = 0
	(t, k) = map(int, input().split())
	ans += (k + 2) * (t // 2)
	if t % 2 == 1:
		ans += 1 + 2 * k
	print(ans)