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.

import java.io.OutputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
//import java.math.*;
 
/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
 
public class Main {
	
	static int MD= 998244353 ;
	static int N=300000;
    public static void main(String[] args) throws IOException {
    	OutputStream outputStream = System.out;
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }
   

	static class TaskC {
    	 
	    public void solve(int testNumber, InputReader in, PrintWriter out) throws IOException {
	    	 
	    	int t=in.nextInt();
	    	while(t-->0) { 
	    		int n=in.nextInt();
	    		int m=in.nextInt();
	    		int ans=n/m*m;
	    		ans+=Math.min(n%m, m/2);
	    		out.println(ans);
	    			
	    	}
	    }
	    	
	}
	   
	
    
    static long modexp(long x, long n) 
    { 
        if (n == 0) { 
            return 1; 
        } 
        else if (n % 2 == 0) { 
            return modexp((x * x) % MD, n / 2); 
        } 
        else { 
            return (x * modexp((x * x) % MD, (n - 1) / 2) % MD); 
        } 
    } 
      
     static long getInv(long b) 
    { 
      
        long  d = modexp(b, MD - 2); 
      
        long ans =  (d % MD) ;
      
        return ans; 
    } 
    
    static class InputReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public InputReader()
        {
            br = new BufferedReader(new
                     InputStreamReader(System.in));
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
   
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    
    }
    static void sort(int[] a, int low, int high) 
    {
        int N = high - low;         
        if (N <= 1) 
            return; 
        int mid = low + N/2; 
        sort(a, low, mid); 
        sort(a, mid, high); 
        int[] temp = new int[N];
        int i = low, j = mid;
        for (int k = 0; k < N; k++) 
        {
            if (i == mid)  
                temp[k] = a[j++];
            else if (j == high) 
                temp[k] = a[i++];
            else if (a[j]<a[i]) 
                temp[k] = a[j++];
            else 
                temp[k] = a[i++];
        }    
        for (int k = 0; k < N; k++) 
            a[low + k] = temp[k];         
    }
    static void lsort(long[] a, int low, int high) 
    {
        int N = high - low;         
        if (N <= 1) 
            return; 
        int mid = low + N/2; 
        lsort(a, low, mid); 
        lsort(a, mid, high); 
        long[] temp = new long[N];
        int i = low, j = mid;
        for (int k = 0; k < N; k++) 
        {
            if (i == mid)  
                temp[k] = a[j++];
            else if (j == high) 
                temp[k] = a[i++];
            else if (a[j]<a[i]) 
                temp[k] = a[j++];
            else 
                temp[k] = a[i++];
        }    
        for (int k = 0; k < N; k++) 
            a[low + k] = temp[k];         
    }
    public static long fexp(long x, long y, long p) {
        long res = 1;      
        
       
        x = x % p;  
      
        while (y > 0) 
        { 
         
            if((y & 1)==1) 
                res = (res * x) % p; 
      
          
            y = y >> 1;  
            x = (x * x) % p;  
        } 
        return res; 
        
    }
    static int gcd(int a, int b) 
    { 
        if (b == 0) 
            return a; 
        return gcd(b, a % b);  
          
    }
    static long lgcd(long a, long b) 
    { 
        if (b == 0) 
            return a; 
        return lgcd(b, a % b);  
          
    }
   
	
	
}
 
