Santa has $n$ candies and he wants to gift them to $k$ kids. He wants to divide as many candies as possible between all $k$ kids. Santa can't divide one candy into parts but he is allowed to not use some candies at all.

Suppose the kid who recieves the minimum number of candies has $a$ candies and the kid who recieves the maximum number of candies has $b$ candies. Then Santa will be satisfied, if the both conditions are met at the same time:

  $b - a \le 1$ (it means $b = a$ or $b = a + 1$);  the number of kids who has $a+1$ candies (note that $a+1$ not necessarily equals $b$) does not exceed $\lfloor\frac{k}{2}\rfloor$ (less than or equal to $\lfloor\frac{k}{2}\rfloor$). 

$\lfloor\frac{k}{2}\rfloor$ is $k$ divided by $2$ and rounded down to the nearest integer. For example, if $k=5$ then $\lfloor\frac{k}{2}\rfloor=\lfloor\frac{5}{2}\rfloor=2$.

Your task is to find the maximum number of candies Santa can give to kids so that he will be satisfied.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 5 \cdot 10^4$) — the number of test cases.

The next $t$ lines describe test cases. The $i$-th test case contains two integers $n$ and $k$ ($1 \le n, k \le 10^9$) — the number of candies and the number of kids.


-----Output-----

For each test case print the answer on it — the maximum number of candies Santa can give to kids so that he will be satisfied.


-----Example-----
Input
5
5 2
19 4
12 7
6 2
100000 50010

Output
5
18
10
6
75015



-----Note-----

In the first test case, Santa can give $3$ and $2$ candies to kids. There $a=2, b=3,a+1=3$.

In the second test case, Santa can give $5, 5, 4$ and $4$ candies. There $a=4,b=5,a+1=5$. The answer cannot be greater because then the number of kids with $5$ candies will be $3$.

In the third test case, Santa can distribute candies in the following way: $[1, 2, 2, 1, 1, 2, 1]$. There $a=1,b=2,a+1=2$. He cannot distribute two remaining candies in a way to be satisfied.

In the fourth test case, Santa can distribute candies in the following way: $[3, 3]$. There $a=3, b=3, a+1=4$. Santa distributed all $6$ candies.

Difficulty: introductory

Starter code:

Solutions:
q = int(input())
for z in range(q):
    n, k = map(int, input().split())
    x = n // k
    n -= x * k
    m = min(k // 2, n)
    print(x * k + m)

t = int(input())
for i in range(t):
	n, k = list(map(int, input().split()))
	z = n // k
	n -= z * k
	print(z * k + min(n, k // 2))


import sys
input = sys.stdin.readline

t=int(input())
for test in range(t):
    n,k=list(map(int,input().split()))

    if n%k>k//2:
        n-=(n%k)-k//2

    print(n)



import sys
import collections
from collections import Counter
import itertools
import math
import timeit

#########################
# imgur.com/Pkt7iIf.png #
#########################

def sieve(n):
    if n < 2: return list()
    prime = [True for _ in range(n + 1)]
    p = 3
    while p * p <= n:
        if prime[p]:
            for i in range(p * 2, n + 1, p):
                prime[i] = False
        p += 2
    r = [2]
    for p in range(3, n + 1, 2):
        if prime[p]:
            r.append(p)
    return r

def divs(n, start=1):
    divisors = []
    for i in range(start, int(math.sqrt(n) + 1)):
        if n % i == 0:
            if n / i == i:
                divisors.append(i)
            else:
                divisors.extend([i, n // i])
    return divisors

def divn(n, primes):
    divs_number = 1
    for i in primes:
        if n == 1:
            return divs_number
        t = 1
        while n % i == 0:
            t += 1
            n //= i
        divs_number *= t

def flin(d, x, default=-1):
    left = right = -1
    for i in range(len(d)):
        if d[i] == x:
            if left == -1: left = i
            right = i
    if left == -1:
        return (default, default)
    else:
        return (left, right)

def ceil(n, k): return n // k + (n % k != 0)
def ii(): return int(input())
def mi(): return list(map(int, input().split()))
def li(): return list(map(int, input().split()))
def lcm(a, b): return abs(a * b) // math.gcd(a, b)
def prr(a, sep=' '): print(sep.join(map(str, a)))
def dd(): return collections.defaultdict(int)
def ddl(): return collections.defaultdict(list)

# input = sys.stdin.readline

t = ii()
for _ in range(t):
    n, k = mi()
    q = n // k
    print(min(n, q * k + (k // 2)))


t = int(input())
for i in range(t):
	n, k = list(map(int, input().split()))
	n1 = n % k
	k1 = int(k / 2)
	if n1 <= k1:
		print(n)
	else:
		print(n - n1 + k1)


q=int(input())
for i in range(q):
    n,k=map(int,input().split())
    ans=n//k*k+min(n%k,k//2)
    print(ans)

a = int(input())
for i in range(a):
    x, y = map(int, input().split())
    u = x//y
    o = x%y
    print(u*y + min(o, y//2))

import sys
# from collections import defaultdict
t=1
t=int(input())
for i in range(t):
    n,m=list(map(int,sys.stdin.readline().strip().split()))
    # a=list(map(int,sys.stdin.readline().strip().split()))
    # b=list(map(int,sys.stdin.readline().strip().split()))
    # d = defaultdict(int)
    # print((24-n-1)*60+60-m)
    x=n//m
    n
    print(x*m+min(n-x*m,m//2))
    


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

q = int(input())
for iwer in range(q):
	c, kids = map(int,input().split())
	dystr = (c//kids)*kids
	cc = c
	c -= dystr
	poz = max(0, c - kids//2)
	print(cc-poz)

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


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))

def solve():
	n, k = mints()
	x = n // k
	r = n % k
	if r > k // 2:
		print(n - (r - k//2))
	else:
		print(n)

for i in range(mint()):
	solve()


from sys import stdin,stdout
tt=int(stdin.readline().strip())
for t in range(tt):
    n,k=list(map(int,stdin.readline().strip().split()))
    x=n//k
    y=n-x*k
    ans=x*k+min(k//2,y)
    print(ans)




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


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


import sys
input = sys.stdin.readline
def getInt(): return int(input())
def getVars(): return list(map(int, input().split()))
def getList(): return list(map(int, input().split()))
def getStr(): return input().strip()
## -------------------------------

t= getInt()
for _ in range(t):
    n, k = getVars()
    m = n // k
    if m*k == n:
        print(n)
        continue
    m1 = k//2
    res = min(n, m*k + m1)
    print(res)



for tc in range(int(input())):
    ncand, nkid = list(map(int, input().split()))
    res = (ncand//nkid)*nkid
    ncand -= res
    res += min(ncand, nkid//2)
    print(res)
        


for nt in range(int(input())):
	n,k=map(int,input().split())
	a=n%k
	if a>k//2:
		print (n-(a-k//2))
	else:
		print (n)

import math
from decimal import Decimal
import heapq
from collections import deque
def na():
	n = int(input())
	b = [int(x) for x in input().split()]
	return n,b
 
 
def nab():
	n = int(input())
	b = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	return n,b,c
 
 
def dv():
	n, m = list(map(int, input().split()))
	return n,m
 
 
def da():
	n, m = list(map(int, input().split()))
	a = list(map(int, input().split()))
	return n,m, a 
 
 
def dva():
	n, m = list(map(int, input().split()))
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	return n,m,b
 
 
def eratosthenes(n): 
	sieve = list(range(n + 1))
	for i in sieve:
		if i > 1:
			for j in range(i + i, len(sieve), i):
				sieve[j] = 0
	return sorted(set(sieve))
 
 
def lol(lst,k):
	k=k%len(lst)
	ret=[0]*len(lst)
	for i in range(len(lst)):
		if i+k<len(lst) and i+k>=0:
			ret[i]=lst[i+k]
		if i+k>=len(lst):
			ret[i]=lst[i+k-len(lst)]
		if i+k<0:
			ret[i]=lst[i+k+len(lst)]
	return(ret)
def nm():
	n = int(input())
	b = [int(x) for x in input().split()]
	m = int(input())
	c = [int(x) for x in input().split()]
	return n,b,m,c
 
 
def dvs():
	n = int(input())
	m = int(input())
	return n, m 
 

def fact(a, b):
	c = []
	ans = 0
	f = int(math.sqrt(a))
	for i in range(1, f + 1):
		if a % i == 0:
			c.append(i)
	l = len(c)
	for i in range(l):
		c.append(a // c[i])
	for i in range(len(c)):
		if c[i] <= b:
			ans += 1
	if a / f == f and b >= f:
		return ans - 1
	return ans


import math
from decimal import Decimal
import heapq
from collections import deque
def na():
	n = int(input())
	b = [int(x) for x in input().split()]
	return n,b
 
 
def nab():
	n = int(input())
	b = [int(x) for x in input().split()]
	c = [int(x) for x in input().split()]
	return n,b,c
 
 
def dv():
	n, m = list(map(int, input().split()))
	return n,m
 
 
def da():
	n, m = list(map(int, input().split()))
	a = list(map(int, input().split()))
	return n,m, a 
 
 
def dva():
	n, m = list(map(int, input().split()))
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	return n,m,b
 
 
def eratosthenes(n): 
	sieve = list(range(n + 1))
	for i in sieve:
		if i > 1:
			for j in range(i + i, len(sieve), i):
				sieve[j] = 0
	return sorted(set(sieve))
 
 
def lol(lst,k):
	k=k%len(lst)
	ret=[0]*len(lst)
	for i in range(len(lst)):
		if i+k<len(lst) and i+k>=0:
			ret[i]=lst[i+k]
		if i+k>=len(lst):
			ret[i]=lst[i+k-len(lst)]
		if i+k<0:
			ret[i]=lst[i+k+len(lst)]
	return(ret)
def nm():
	n = int(input())
	b = [int(x) for x in input().split()]
	m = int(input())
	c = [int(x) for x in input().split()]
	return n,b,m,c
 
 
def dvs():
	n = int(input())
	m = int(input())
	return n, m 
 
 
def fact(a, b):
	c = []
	ans = 0
	f = int(math.sqrt(a))
	for i in range(1, f + 1):
		if a % i == 0:
			c.append(i)
	l = len(c)
	for i in range(l):
		c.append(a // c[i])
	for i in range(len(c)):
		if c[i] <= b:
			ans += 1
	if a / f == f and b >= f:
		return ans - 1
	return ans
 
 
for i in range(int(input())):
	n, k = list(map(int, input().split()))
	d = n // k
	n -= d * k
	ans = d * k + min(k // 2, n)
	print(ans) 





def main():
    a, b = list(map(int, input().split()))
    k = b // 2
    print(min(a - (a % b - k), a))



c = int(input())

for i in range(c):
    main()



t = int(input())
for i in range (t):
    n, k = list(map(int,input().split()))
    m = n % k
    print(n - m + min(k//2, m) )

Q = int(input())

for q in range(Q):
    n, k = [int(x) for x in input().split()]
    maximum = (n//k)*k + k//2
    print(min([maximum, n]))

q=int(input())
for i in range(q):
    n,k=list(map(int,input().split()))
    y=n%k
    print((n//k)*k+min(y,k//2))


for _ in range(int(input())):
    n,k = [int(s) for s in input().split()]
    ans = (n//k)*k
    ans1 = n%k
    ans+= min(k//2, ans1)
    print(ans)