#include <bits/stdc++.h>
using namespace std;
long long int mod = 1e9 + 7;
const long long int N = 1e6 + 5;
long long int fact[N + 2];
long long int spf[N];
void sieve() {
  spf[1] = 1;
  for (long long int i = 2; i < N; i++) {
    spf[i] = i;
  }
  for (long long int i = 4; i < N; i += 2) {
    spf[i] = 2;
  }
  for (long long int i = 3; i * i < N; i++) {
    if (spf[i] == i) {
      for (long long int j = i * i; j < N; j += i) {
        if (spf[j] == j) {
          spf[j] = i;
        }
      }
    }
  }
}
long long int mp[N + 1];
void getfacots(long long int x) {
  long long int cnt = 0;
  while (x != 1) {
    mp[spf[x]]++;
    x = x / spf[x];
  }
}
long long int modexp(long long int x, long long int y, long long int p) {
  if (x == 0) {
    return 0;
  }
  if (y == 0) {
    return 1;
  }
  if (y % 2 == 0) {
    long long int res = modexp(x, y / 2, p);
    return (res * res) % p;
  } else {
    long long int res = modexp(x, y - 1, p);
    return (x * res) % p;
  }
}
long long int inverse(long long int n, long long int p) {
  return modexp(n, p - 2, p);
}
long long int ncr(long long int n, long long int r, long long int mod) {
  long long int ans = ((fact[n] % mod * inverse(fact[r], mod) % mod) % mod *
                       inverse(fact[n - r], mod) % mod) %
                      mod;
  return ans;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int t;
  cin >> t;
  while (t--) {
    long long int n, m;
    cin >> n >> m;
    long long int ans;
    long long int r = n % m;
    long long int x = n / m;
    if (r > m / 2) {
      cout << x * m + m / 2 << endl;
    } else {
      cout << n << endl;
    }
  }
  return 0;
}

### Prompt

In cpp, your task is to solve the following problem:

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 ≤ 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 ⌊k/2⌋ (less than or equal to ⌊k/2⌋). 



⌊k/2⌋ is k divided by 2 and rounded down to the nearest integer. For example, if k=5 then ⌊k/2⌋=⌊5/2⌋=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 ≤ t ≤ 5 ⋅ 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 ≤ n, k ≤ 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long int mod = 1e9 + 7;
const long long int N = 1e6 + 5;
long long int fact[N + 2];
long long int spf[N];
void sieve() {
  spf[1] = 1;
  for (long long int i = 2; i < N; i++) {
    spf[i] = i;
  }
  for (long long int i = 4; i < N; i += 2) {
    spf[i] = 2;
  }
  for (long long int i = 3; i * i < N; i++) {
    if (spf[i] == i) {
      for (long long int j = i * i; j < N; j += i) {
        if (spf[j] == j) {
          spf[j] = i;
        }
      }
    }
  }
}
long long int mp[N + 1];
void getfacots(long long int x) {
  long long int cnt = 0;
  while (x != 1) {
    mp[spf[x]]++;
    x = x / spf[x];
  }
}
long long int modexp(long long int x, long long int y, long long int p) {
  if (x == 0) {
    return 0;
  }
  if (y == 0) {
    return 1;
  }
  if (y % 2 == 0) {
    long long int res = modexp(x, y / 2, p);
    return (res * res) % p;
  } else {
    long long int res = modexp(x, y - 1, p);
    return (x * res) % p;
  }
}
long long int inverse(long long int n, long long int p) {
  return modexp(n, p - 2, p);
}
long long int ncr(long long int n, long long int r, long long int mod) {
  long long int ans = ((fact[n] % mod * inverse(fact[r], mod) % mod) % mod *
                       inverse(fact[n - r], mod) % mod) %
                      mod;
  return ans;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int t;
  cin >> t;
  while (t--) {
    long long int n, m;
    cin >> n >> m;
    long long int ans;
    long long int r = n % m;
    long long int x = n / m;
    if (r > m / 2) {
      cout << x * m + m / 2 << endl;
    } else {
      cout << n << endl;
    }
  }
  return 0;
}

```