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.
[{"code": "q = int(input())\nfor z in range(q):\n    n, k = map(int, input().split())\n    x = n // k\n    n -= x * k\n    m = min(k // 2, n)\n    print(x * k + m)", "passed": true, "time": 0.15, "memory": 14192.0, "status": "done"}, {"code": "t = int(input())\nfor i in range(t):\n\tn, k = list(map(int, input().split()))\n\tz = n // k\n\tn -= z * k\n\tprint(z * k + min(n, k // 2))\n", "passed": true, "time": 0.16, "memory": 14232.0, "status": "done"}, {"code": "import sys\ninput = sys.stdin.readline\n\nt=int(input())\nfor test in range(t):\n    n,k=list(map(int,input().split()))\n\n    if n%k>k//2:\n        n-=(n%k)-k//2\n\n    print(n)\n\n", "passed": true, "time": 0.15, "memory": 14300.0, "status": "done"}, {"code": "import sys\nimport collections\nfrom collections import Counter\nimport itertools\nimport math\nimport timeit\n\n#########################\n# imgur.com/Pkt7iIf.png #\n#########################\n\ndef sieve(n):\n    if n < 2: return list()\n    prime = [True for _ in range(n + 1)]\n    p = 3\n    while p * p <= n:\n        if prime[p]:\n            for i in range(p * 2, n + 1, p):\n                prime[i] = False\n        p += 2\n    r = [2]\n    for p in range(3, n + 1, 2):\n        if prime[p]:\n            r.append(p)\n    return r\n\ndef divs(n, start=1):\n    divisors = []\n    for i in range(start, int(math.sqrt(n) + 1)):\n        if n % i == 0:\n            if n / i == i:\n                divisors.append(i)\n            else:\n                divisors.extend([i, n // i])\n    return divisors\n\ndef divn(n, primes):\n    divs_number = 1\n    for i in primes:\n        if n == 1:\n            return divs_number\n        t = 1\n        while n % i == 0:\n            t += 1\n            n //= i\n        divs_number *= t\n\ndef flin(d, x, default=-1):\n    left = right = -1\n    for i in range(len(d)):\n        if d[i] == x:\n            if left == -1: left = i\n            right = i\n    if left == -1:\n        return (default, default)\n    else:\n        return (left, right)\n\ndef ceil(n, k): return n // k + (n % k != 0)\ndef ii(): return int(input())\ndef mi(): return list(map(int, input().split()))\ndef li(): return list(map(int, input().split()))\ndef lcm(a, b): return abs(a * b) // math.gcd(a, b)\ndef prr(a, sep=' '): print(sep.join(map(str, a)))\ndef dd(): return collections.defaultdict(int)\ndef ddl(): return collections.defaultdict(list)\n\n# input = sys.stdin.readline\n\nt = ii()\nfor _ in range(t):\n    n, k = mi()\n    q = n // k\n    print(min(n, q * k + (k // 2)))\n", "passed": true, "time": 1.69, "memory": 14228.0, "status": "done"}, {"code": "t = int(input())\nfor i in range(t):\n\tn, k = list(map(int, input().split()))\n\tn1 = n % k\n\tk1 = int(k / 2)\n\tif n1 <= k1:\n\t\tprint(n)\n\telse:\n\t\tprint(n - n1 + k1)\n", "passed": true, "time": 0.16, "memory": 14152.0, "status": "done"}, {"code": "q=int(input())\nfor i in range(q):\n    n,k=map(int,input().split())\n    ans=n//k*k+min(n%k,k//2)\n    print(ans)", "passed": true, "time": 0.15, "memory": 14316.0, "status": "done"}, {"code": "a = int(input())\nfor i in range(a):\n    x, y = map(int, input().split())\n    u = x//y\n    o = x%y\n    print(u*y + min(o, y//2))", "passed": true, "time": 0.2, "memory": 14292.0, "status": "done"}, {"code": "import sys\n# from collections import defaultdict\nt=1\nt=int(input())\nfor i in range(t):\n    n,m=list(map(int,sys.stdin.readline().strip().split()))\n    # a=list(map(int,sys.stdin.readline().strip().split()))\n    # b=list(map(int,sys.stdin.readline().strip().split()))\n    # d = defaultdict(int)\n    # print((24-n-1)*60+60-m)\n    x=n//m\n    n\n    print(x*m+min(n-x*m,m//2))\n    \n", "passed": true, "time": 1.66, "memory": 14252.0, "status": "done"}, {"code": "t=int(input())\nwhile t:\n    n,k=map(int,input().split())\n    print(n-max(0,n%k-k//2))\n    t-=1", "passed": true, "time": 0.14, "memory": 14060.0, "status": "done"}, {"code": "q = int(input())\nfor iwer in range(q):\n\tc, kids = map(int,input().split())\n\tdystr = (c//kids)*kids\n\tcc = c\n\tc -= dystr\n\tpoz = max(0, c - kids//2)\n\tprint(cc-poz)", "passed": true, "time": 0.16, "memory": 14100.0, "status": "done"}, {"code": "t = int(input())\nfor i in range(t):\n    n, k = list(map(int, input().split()))\n    if n % k <= k // 2:\n        print(n)\n    else:\n        print((n // k) * k + k // 2)\n", "passed": true, "time": 0.14, "memory": 14188.0, "status": "done"}, {"code": "import sys\n\ndef minp():\n\treturn sys.stdin.readline().strip()\n\ndef mint():\n\treturn int(minp())\n\ndef mints():\n\treturn list(map(int, minp().split()))\n\ndef solve():\n\tn, k = mints()\n\tx = n // k\n\tr = n % k\n\tif r > k // 2:\n\t\tprint(n - (r - k//2))\n\telse:\n\t\tprint(n)\n\nfor i in range(mint()):\n\tsolve()\n", "passed": true, "time": 0.16, "memory": 14096.0, "status": "done"}, {"code": "from sys import stdin,stdout\ntt=int(stdin.readline().strip())\nfor t in range(tt):\n    n,k=list(map(int,stdin.readline().strip().split()))\n    x=n//k\n    y=n-x*k\n    ans=x*k+min(k//2,y)\n    print(ans)\n\n\n", "passed": true, "time": 0.15, "memory": 14140.0, "status": "done"}, {"code": "T = int(input())\nfor _ in range(T):\n  n,k = list(map(int, input().split()))\n  print(n//k*k + min(n%k, int(k/2)))\n", "passed": true, "time": 0.22, "memory": 14264.0, "status": "done"}, {"code": "for _ in range(int(input())):\n    n,k = list(map(int, input().split()))\n    ans = (n//k)*k + min(k//2,n%k)\n    print(ans)\n", "passed": true, "time": 0.14, "memory": 14104.0, "status": "done"}, {"code": "import sys\ninput = sys.stdin.readline\ndef getInt(): return int(input())\ndef getVars(): return list(map(int, input().split()))\ndef getList(): return list(map(int, input().split()))\ndef getStr(): return input().strip()\n## -------------------------------\n\nt= getInt()\nfor _ in range(t):\n    n, k = getVars()\n    m = n // k\n    if m*k == n:\n        print(n)\n        continue\n    m1 = k//2\n    res = min(n, m*k + m1)\n    print(res)\n\n", "passed": true, "time": 0.27, "memory": 14284.0, "status": "done"}, {"code": "for tc in range(int(input())):\n    ncand, nkid = list(map(int, input().split()))\n    res = (ncand//nkid)*nkid\n    ncand -= res\n    res += min(ncand, nkid//2)\n    print(res)\n        \n", "passed": true, "time": 0.14, "memory": 14324.0, "status": "done"}, {"code": "for nt in range(int(input())):\n\tn,k=map(int,input().split())\n\ta=n%k\n\tif a>k//2:\n\t\tprint (n-(a-k//2))\n\telse:\n\t\tprint (n)", "passed": true, "time": 0.14, "memory": 14276.0, "status": "done"}, {"code": "import math\nfrom decimal import Decimal\nimport heapq\nfrom collections import deque\ndef na():\n\tn = int(input())\n\tb = [int(x) for x in input().split()]\n\treturn n,b\n \n \ndef nab():\n\tn = int(input())\n\tb = [int(x) for x in input().split()]\n\tc = [int(x) for x in input().split()]\n\treturn n,b,c\n \n \ndef dv():\n\tn, m = list(map(int, input().split()))\n\treturn n,m\n \n \ndef da():\n\tn, m = list(map(int, input().split()))\n\ta = list(map(int, input().split()))\n\treturn n,m, a \n \n \ndef dva():\n\tn, m = list(map(int, input().split()))\n\ta = [int(x) for x in input().split()]\n\tb = [int(x) for x in input().split()]\n\treturn n,m,b\n \n \ndef eratosthenes(n): \n\tsieve = list(range(n + 1))\n\tfor i in sieve:\n\t\tif i > 1:\n\t\t\tfor j in range(i + i, len(sieve), i):\n\t\t\t\tsieve[j] = 0\n\treturn sorted(set(sieve))\n \n \ndef lol(lst,k):\n\tk=k%len(lst)\n\tret=[0]*len(lst)\n\tfor i in range(len(lst)):\n\t\tif i+k<len(lst) and i+k>=0:\n\t\t\tret[i]=lst[i+k]\n\t\tif i+k>=len(lst):\n\t\t\tret[i]=lst[i+k-len(lst)]\n\t\tif i+k<0:\n\t\t\tret[i]=lst[i+k+len(lst)]\n\treturn(ret)\ndef nm():\n\tn = int(input())\n\tb = [int(x) for x in input().split()]\n\tm = int(input())\n\tc = [int(x) for x in input().split()]\n\treturn n,b,m,c\n \n \ndef dvs():\n\tn = int(input())\n\tm = int(input())\n\treturn n, m \n \n\ndef fact(a, b):\n\tc = []\n\tans = 0\n\tf = int(math.sqrt(a))\n\tfor i in range(1, f + 1):\n\t\tif a % i == 0:\n\t\t\tc.append(i)\n\tl = len(c)\n\tfor i in range(l):\n\t\tc.append(a // c[i])\n\tfor i in range(len(c)):\n\t\tif c[i] <= b:\n\t\t\tans += 1\n\tif a / f == f and b >= f:\n\t\treturn ans - 1\n\treturn ans\n\n\nimport math\nfrom decimal import Decimal\nimport heapq\nfrom collections import deque\ndef na():\n\tn = int(input())\n\tb = [int(x) for x in input().split()]\n\treturn n,b\n \n \ndef nab():\n\tn = int(input())\n\tb = [int(x) for x in input().split()]\n\tc = [int(x) for x in input().split()]\n\treturn n,b,c\n \n \ndef dv():\n\tn, m = list(map(int, input().split()))\n\treturn n,m\n \n \ndef da():\n\tn, m = list(map(int, input().split()))\n\ta = list(map(int, input().split()))\n\treturn n,m, a \n \n \ndef dva():\n\tn, m = list(map(int, input().split()))\n\ta = [int(x) for x in input().split()]\n\tb = [int(x) for x in input().split()]\n\treturn n,m,b\n \n \ndef eratosthenes(n): \n\tsieve = list(range(n + 1))\n\tfor i in sieve:\n\t\tif i > 1:\n\t\t\tfor j in range(i + i, len(sieve), i):\n\t\t\t\tsieve[j] = 0\n\treturn sorted(set(sieve))\n \n \ndef lol(lst,k):\n\tk=k%len(lst)\n\tret=[0]*len(lst)\n\tfor i in range(len(lst)):\n\t\tif i+k<len(lst) and i+k>=0:\n\t\t\tret[i]=lst[i+k]\n\t\tif i+k>=len(lst):\n\t\t\tret[i]=lst[i+k-len(lst)]\n\t\tif i+k<0:\n\t\t\tret[i]=lst[i+k+len(lst)]\n\treturn(ret)\ndef nm():\n\tn = int(input())\n\tb = [int(x) for x in input().split()]\n\tm = int(input())\n\tc = [int(x) for x in input().split()]\n\treturn n,b,m,c\n \n \ndef dvs():\n\tn = int(input())\n\tm = int(input())\n\treturn n, m \n \n \ndef fact(a, b):\n\tc = []\n\tans = 0\n\tf = int(math.sqrt(a))\n\tfor i in range(1, f + 1):\n\t\tif a % i == 0:\n\t\t\tc.append(i)\n\tl = len(c)\n\tfor i in range(l):\n\t\tc.append(a // c[i])\n\tfor i in range(len(c)):\n\t\tif c[i] <= b:\n\t\t\tans += 1\n\tif a / f == f and b >= f:\n\t\treturn ans - 1\n\treturn ans\n \n \nfor i in range(int(input())):\n\tn, k = list(map(int, input().split()))\n\td = n // k\n\tn -= d * k\n\tans = d * k + min(k // 2, n)\n\tprint(ans) \n", "passed": true, "time": 0.14, "memory": 14616.0, "status": "done"}, {"code": "\n\n\ndef main():\n    a, b = list(map(int, input().split()))\n    k = b // 2\n    print(min(a - (a % b - k), a))\n\n\n\nc = int(input())\n\nfor i in range(c):\n    main()\n\n", "passed": true, "time": 0.14, "memory": 14260.0, "status": "done"}, {"code": "t = int(input())\nfor i in range (t):\n    n, k = list(map(int,input().split()))\n    m = n % k\n    print(n - m + min(k//2, m) )", "passed": true, "time": 0.14, "memory": 14320.0, "status": "done"}, {"code": "Q = int(input())\n\nfor q in range(Q):\n    n, k = [int(x) for x in input().split()]\n    maximum = (n//k)*k + k//2\n    print(min([maximum, n]))", "passed": true, "time": 0.14, "memory": 14204.0, "status": "done"}, {"code": "q=int(input())\nfor i in range(q):\n    n,k=list(map(int,input().split()))\n    y=n%k\n    print((n//k)*k+min(y,k//2))\n", "passed": true, "time": 0.14, "memory": 14084.0, "status": "done"}, {"code": "for _ in range(int(input())):\n    n,k = [int(s) for s in input().split()]\n    ans = (n//k)*k\n    ans1 = n%k\n    ans+= min(k//2, ans1)\n    print(ans)", "passed": true, "time": 0.14, "memory": 14100.0, "status": "done"}]