#include <bits/stdc++.h>
using namespace std;
template <typename TH>
void _dbg(const char *sdbg, TH h) {
  cerr << sdbg << "=" << h << "\n";
}
template <typename TH, typename... TA>
void _dbg(const char *sdbg, TH h, TA... t) {
  while (*sdbg != ',') {
    cerr << *sdbg++;
  }
  cerr << "=" << h << ",";
  _dbg(sdbg + 1, t...);
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
};
template <class T>
T lcm(T a, T b) {
  return a * b / gcd(a, b);
};
vector<string> split(string s) {
  istringstream buf(s);
  istream_iterator<string> beg(buf), end;
  vector<string> list(beg, end);
  return list;
}
bool isvowel(char c) {
  string s = "aeiouAEIOU";
  if (find(s.begin(), s.end(), c) != s.end()) return true;
  return false;
}
vector<long long> sieve(long long n) {
  vector<bool> prime(n + 1, true);
  prime[0] = prime[1] = 0;
  for (int i = 2; i * i <= n; i++) {
    if (prime[i])
      for (int j = i * i; j <= n; j += i) {
        prime[j] = 0;
      }
  }
  vector<long long> p;
  for (int i = 2; i <= prime.size(); i++)
    if (prime[i]) p.push_back(i);
  return p;
}
bool isprime(int n) {
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true && (n != 1);
}
int ncr(long long n, long long r) {
  long long C[r + 1];
  memset(C, 0, sizeof(C));
  C[0] = 1;
  for (long long i = 1; i <= n; i++) {
    for (long long j = min(i, r); j > 0; j--)
      C[j] = (C[j] + C[j - 1]) % 1000000007;
  }
  return C[r];
}
void solve() {
  long long n, k;
  cin >> n >> k;
  cout << n / k * k + min(k / 2, n % k) << endl;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int t = 1;
  cin >> t;
  for (int test_case = 1; test_case <= t; test_case++) {
    solve();
  }
  return 0;
}

### Prompt

Generate a cpp solution to 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;
template <typename TH>
void _dbg(const char *sdbg, TH h) {
  cerr << sdbg << "=" << h << "\n";
}
template <typename TH, typename... TA>
void _dbg(const char *sdbg, TH h, TA... t) {
  while (*sdbg != ',') {
    cerr << *sdbg++;
  }
  cerr << "=" << h << ",";
  _dbg(sdbg + 1, t...);
}
template <class T>
T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
};
template <class T>
T lcm(T a, T b) {
  return a * b / gcd(a, b);
};
vector<string> split(string s) {
  istringstream buf(s);
  istream_iterator<string> beg(buf), end;
  vector<string> list(beg, end);
  return list;
}
bool isvowel(char c) {
  string s = "aeiouAEIOU";
  if (find(s.begin(), s.end(), c) != s.end()) return true;
  return false;
}
vector<long long> sieve(long long n) {
  vector<bool> prime(n + 1, true);
  prime[0] = prime[1] = 0;
  for (int i = 2; i * i <= n; i++) {
    if (prime[i])
      for (int j = i * i; j <= n; j += i) {
        prime[j] = 0;
      }
  }
  vector<long long> p;
  for (int i = 2; i <= prime.size(); i++)
    if (prime[i]) p.push_back(i);
  return p;
}
bool isprime(int n) {
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true && (n != 1);
}
int ncr(long long n, long long r) {
  long long C[r + 1];
  memset(C, 0, sizeof(C));
  C[0] = 1;
  for (long long i = 1; i <= n; i++) {
    for (long long j = min(i, r); j > 0; j--)
      C[j] = (C[j] + C[j - 1]) % 1000000007;
  }
  return C[r];
}
void solve() {
  long long n, k;
  cin >> n >> k;
  cout << n / k * k + min(k / 2, n % k) << endl;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int t = 1;
  cin >> t;
  for (int test_case = 1; test_case <= t; test_case++) {
    solve();
  }
  return 0;
}

```