The game of Berland poker is played with a deck of n cards, m of which are jokers. k players play this game (n is divisible by k).

At the beginning of the game, each player takes n/k cards from the deck (so each card is taken by exactly one player). The player who has the maximum number of jokers is the winner, and he gets the number of points equal to x - y, where x is the number of jokers in the winner's hand, and y is the maximum number of jokers among all other players. If there are two or more players with maximum number of jokers, all of them are winners and they get 0 points.

Here are some examples:

  * n = 8, m = 3, k = 2. If one player gets 3 jokers and 1 plain card, and another player gets 0 jokers and 4 plain cards, then the first player is the winner and gets 3 - 0 = 3 points; 
  * n = 4, m = 2, k = 4. Two players get plain cards, and the other two players get jokers, so both of them are winners and get 0 points; 
  * n = 9, m = 6, k = 3. If the first player gets 3 jokers, the second player gets 1 joker and 2 plain cards, and the third player gets 2 jokers and 1 plain card, then the first player is the winner, and he gets 3 - 2 = 1 point; 
  * n = 42, m = 0, k = 7. Since there are no jokers, everyone gets 0 jokers, everyone is a winner, and everyone gets 0 points. 



Given n, m and k, calculate the maximum number of points a player can get for winning the game.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 500) — the number of test cases.

Then the test cases follow. Each test case contains three integers n, m and k (2 ≤ n ≤ 50, 0 ≤ m ≤ n, 2 ≤ k ≤ n, k is a divisors of n).

Output

For each test case, print one integer — the maximum number of points a player can get for winning the game.

Example

Input


4
8 3 2
4 2 4
9 6 3
42 0 7


Output


3
0
1
0

Note

Test cases of the example are described in the statement.
import java.io.*;
import java.math.*;
import java.util.*;
import java.lang.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import static java.util.stream.IntStream.of;

public final class Code2 {

    static FastIO2 rd = new FastIO2();
    static Scanner sc = new Scanner(System.in);
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(System.out);
    static Random rand = new Random();

    public static void main(String[] args) {
        try {

            // FileReader fr=new FileReader("E:\\Github\\Competition\\inp.txt");

            
            int t=nxti();
            while(t-->0){

                int[] inp=nxtira();
                int n=inp[0];
                int m=inp[1];
                int k=inp[2];

                int x=n/k;

                if(x>=m)prln(m);
                else {
                    int[] a=new int[k];
                    a[0]=x;

                    int i=1;
                    int dec=m-x;

                    while(dec!=0){
                        if(i%k!=0){
                            a[i%k]++;
                            dec--;
                        }
                        i++;
                    }

                    // dbgra(a);
                    int max=Integer.MIN_VALUE;
                    for (i = 1; i < a.length; i++) {
                        if(a[i]>max)max=a[i];
                    }
                    prln(a[0]-max);
                }
                
            }
            flush();
            close();


        } catch (Exception e) {rd.println(e);}

    }

    
    public static String swap(String s, int i, int j) {
        char[] ch=s.toCharArray();

        char temp = ch[i];
        ch[i] = ch[j];
        ch[j] = temp;

        // dbgra(ch);
        String newstr=new String(ch);
        return newstr;
    }

    
    
    
    
    static void dbgra(int[] a) {prln(Arrays.toString(a));}
    static void dbgra(long[] a) {prln(Arrays.toString(a));}
    static void dbgra(String[] a) {prln(Arrays.toString(a));}
    static void dbgra(char[] a) {prln(Arrays.toString(a));}
    static void dbgra(Integer[] a) {prln(Arrays.toString(a));}
    static void dbgra(Set<Integer> a) {prln(a.toString());}
    static void dbgral(ArrayList<Integer> al) {prln(al.toString());}
    static void dbgrall(ArrayList<Long> al) {prln(al.toString());}
    static void dbgrald(ArrayList<Double> al) {prln(al.toString());}
    static void dbgrals(ArrayList<String> al) {prln(al.toString());}
    
    // Global variables
    static int count = 0, temp = 0, max = 0, min = 0, sum = 0, fact = 1, prod = 1, n,m,k;
    
    static int size = 0;
    static char c;
    static String str = new String();
    static String str1 = new String();
    static String[] ras = new String[size];
    static int[] rai = new int[size];
    static int[] ch = new int[size];
    static long[] ral = new long[size];
    static ArrayList<String> rals = new ArrayList<>();
    static ArrayList<Integer> rali = new ArrayList<>();
    static ArrayList<Integer> al = new ArrayList<>();
    static ArrayList<Integer> al1 = new ArrayList<>();
    static ArrayList<Integer> al2 = new ArrayList<>();
    static ArrayList<Long> rall = new ArrayList<>();
    static ArrayList<Double> rald = new ArrayList<>();
    
    // references
    // IBIG = 1e9 + 7
    // IRAND ~= 3e8
    // IMAX ~= 2e10
    // LMAX ~= 9e18
    // constants
    static final int IBIG = 1000000007;
    static final int IRAND = 327859546;
    static final int IMAX = 2147483647;
    static final int IMIN = -2147483648;
    static final long LMAX = 9223372036854775807L;
    static final long LMIN = -9223372036854775808L;
    
    // math util
    static int min(int a,int b){return a<b?a:b;}
    static long min(long a,long b){return a<b?a:b;}
    static int max(int a,int b){return a>b?a:b;}
    static long max(long a,long b){return a>b?a:b;}
    static int minof(int a, int b, int c) {return min(a, min(b, c));}
    static int min(int... x) {if(x.length == 1) return x[0]; if(x.length == 2) return min(x[0], x[1]); if(x.length == 3) return min(x[0], min(x[1], x[2])); int min = x[0]; for(int i = 1; i < x.length; ++i) if(x[i] < min) min = x[i]; return min;}
    static int min(int a, int b, int c) {return min(a, min(b, c));}
    static long min(long a, long b, long c) {return min(a, min(b, c));}
    static long min(long... x) {if(x.length == 1) return x[0]; if(x.length == 2) return min(x[0], x[1]); if(x.length == 3) return min(x[0], min(x[1], x[2])); long min = x[0]; for(int i = 1; i < x.length; ++i) if(x[i] < min) min = x[i]; return min;}
    static int max(int a, int b, int c) {return max(a, max(b, c));}
    static int max(int... x) {if(x.length == 1) return x[0]; if(x.length == 2) return max(x[0], x[1]); if(x.length == 3) return max(x[0], max(x[1], x[2])); int max = x[0]; for(int i = 1; i < x.length; ++i) if(x[i] > max) max = x[i]; return max;}
    static long max(long a, long b, long c) {return max(a, max(b, c));}
    static long max(long... x) {if(x.length == 1) return x[0]; if(x.length == 2) return max(x[0], x[1]); if(x.length == 3) return max(x[0], max(x[1], x[2])); long max = x[0]; for(int i = 1; i < x.length; ++i) if(x[i] > max) max = x[i]; return max;}
    static int max(ArrayList<Integer> al) {return Collections.max(al);}
    static int min(ArrayList<Integer> al) {return Collections.min(al);}
    static int count(int n){return floori(Math.log10(n))+1;}
    static int count(long n){return (int)(Math.floor(Math.log10(n))+1);}
    static int count(String s , char c){int count=0;for (int i = 0; i < s.length(); i++) {if(s.charAt(i)==c)count++;}return count;}
    static int count(char[] s , char c){int count=0;for (int i = 0; i < s.length; i++) {if(s[i]==c)count++;}return count;}
    static int count(int[] s , int c){int count=0;for (int i = 0; i < s.length; i++) {if(s[i]==c)count++;}return count;}
    static int count(long[] s , long c){int count=0;for (int i = 0; i < s.length; i++) {if(s[i]==c)count++;}return count;}
    static int count(double[] s , double c){int count=0;for (int i = 0; i < s.length; i++) {if(s[i]==c)count++;}return count;}
    static int count(List<String> s , String c){int count=0;for (int i = 0; i < s.size(); i++) {if(s.get(i)==c)count++;}return count;}
    static int[] countAll(String s){int[] alpha = new int[26];for (int i = 0; i < s.length(); i++) {alpha[(int)s.charAt(i)-97]++;}return alpha;}
    static int powi(int a, int b) {if(a == 0) return 0; int ans = 1; while(b > 0) {if((b & 1) > 0) ans *= a; a *= a; b >>= 1;} return ans;}
    static long powl(long a, int b) {if(a == 0) return 0; long ans = 1; while(b > 0) {if((b & 1) > 0) ans *= a; a *= a; b >>= 1;} return ans;}
    static int sqrt(int n){return (int)Math.sqrt(n);}
    static long sqrt(long n){return (long)Math.sqrt(n);}
    static double sqrt(double n){return Math.sqrt(n);}
    static int floori(double d) {return (int)Math.floor(d);}
    static int ceili(double d) {return (int)Math.ceil(d);}
    static long floorl(double d) {return (long)Math.floor(d);}
    static long ceill(double d) {return (long)Math.ceil(d);}
    static long lcm(long a, long b) {return (a * b) / gcd(a, b);}
    static long gcd(long a, long b) {if (a == 0)return b; return gcd(b % a, a);}
    static int lcm(int a, int b) {return (a * b) / gcd(a, b);}
    static int gcd(int a, int b) {if (a == 0)return b; return gcd(b % a, a);}
    static boolean prime(int n) {for (int i = 2; i <= sqrt(n); i++) {if(n%i==0)return false;}return true ;}
    static int randInt(int min, int max) {return rand.nextInt(max - min + 1) + min;}
    
    // array util
    static boolean vowel(char c) {if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u'||c=='y')return true; else return false ;}
    static void reverse(int[] a) {for(int i = 0, n = a.length, half = n / 2; i < half; ++i) {int swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static void reverse(long[] a) {for(int i = 0, n = a.length, half = n / 2; i < half; ++i) {long swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static void reverse(double[] a) {for(int i = 0, n = a.length, half = n / 2; i < half; ++i) {double swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static void reverse(char[] a) {for(int i = 0, n = a.length, half = n / 2; i < half; ++i) {char swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static <T> void reverse(T[] a) {for(int i = 0, n = a.length, half = n / 2; i < half; ++i) {T swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static void shuffle(int[] a) {int n = a.length - 1; for(int i = 0; i < n; ++i) {int ind = randInt(i, n); int swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static void shuffle(long[] a) {int n = a.length - 1; for(int i = 0; i < n; ++i) {int ind = randInt(i, n); long swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static void shuffle(double[] a) {int n = a.length - 1; for(int i = 0; i < n; ++i) {int ind = randInt(i, n); double swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static void shuffle(char[] a) {int n = a.length - 1; for(int i = 0; i < n; ++i) {int ind = randInt(i, n); char swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static <T> void shuffle(T[] a) {int n = a.length - 1; for(int i = 0; i < n; ++i) {int ind = randInt(i, n); T swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static void rsort(int[] a) {shuffle(a); Arrays.sort(a);}
    static void rsort(long[] a) {shuffle(a); Arrays.sort(a);}
    static void rsort(double[] a) {shuffle(a); Arrays.sort(a);}
    static void rsort(char[] a) {shuffle(a); Arrays.sort(a);}
    static <T> void rsort(T[] a) {shuffle(a); Arrays.sort(a);}
    static String leftPad(String str , int n , String s){String temp="";for (int i = 0; i < n-str.length(); i++) {temp+=s;} temp+=str; return temp;}
    static String rightPad(String str , int n , String s){for (int i = 0; i < n-str.length(); i++) {str+=s;}return str;}
    

    //input
    static int nxti() throws NumberFormatException, IOException {return rd.nextInt();}
    static long nxtl() throws NumberFormatException, IOException {return rd.nextLong();}
    static double nxtd() throws NumberFormatException, IOException {return rd.nextDouble();}
    static char nxtc() throws NumberFormatException, IOException {return rd.nextChar();}
    static String nxt() throws IOException {return rd.next();}
    static int[] nxtira() throws NumberFormatException, IOException {return rd.nextIntArray();}
    // static int[][] nxtira(int r, int c){return rd.nextInt2DArray(r,c);}
    // static long[] nxtlra(int size){return rd.nextLongArray(size);}
    // static long[][] nxtlra(int r, int c){return rd.nextLong2DArray(r,c);}
    // static char[] nxtcra(){return rd.next().toCharArray();}
    // static String[] nxtsra(int size){return rd.nextStringArray(size);}

    // // output
    static void pr(int i) {rd.print(i);}
    static void prln(int i) {rd.println(i);}
    static void pr(long l) {rd.print(l);}
    static void prln(long l) {rd.println(l);}
    static void pr(double d) {rd.print(d);}
    static void prln(double d) {rd.println(d);}
    static void pr(char c) {rd.print(c);}
    static void prln(char c) {rd.println(c);}

    static void prln() {rd.println();}
    static void prln(char[] c) {rd.println(c);}
    static void pr(String s) {rd.print(s);}
    static void prln(String s) {rd.println(s);}
    static void pr(Object o) {System.out.print(o);}
    static void prln(Object o) {System.out.println(o);}
    static void pry() {rd.println("yes");}
    static void prYes() {rd.println("Yes");}
    static void prY() {rd.println("YES");}
    static void prn() {rd.println("no");}
    static void prNo() {rd.println("No");}
    static void prN() {rd.println("NO");}
    static void pryn(boolean b) {rd.println(b ? "yes" : "no");};
    static void prYesNo(boolean b) {System.out.println(b ? "Yes" : "No");}
    static void prYN(boolean b) {System.out.println(b ? "YES" : "NO");}
    static void pr(int[] a){rd.print(a);}
    static void prln(int[] a){rd.println(a);}
    static void pr(long[] a){rd.print(a);}
    static void prln(long[] a){rd.println(a);}
    static void pr(double[] a){rd.print(a);}
    static void prln(double[] a){rd.println(a);}
    static void prln(char[][] a){rd.println(a);}
    static void prln(boolean[][] a){rd.println(a);}
    // static void pr(String[] a){rd.print(a);}
    // static void prln(String[] a){rd.println(a);}
    // // static <T> void prln(Collection<T> c) {int n = c.size() - 1; Iterator<T> iter = c.iterator(); for(int i = 0; i < n; rd.print(iter.next()), rd.print(' '), ++i); rd.println(iter.next());}
    static void flush() {rd.flush();}
    static void close() {rd.close();}
}



class FastIO2{

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out = new PrintWriter(System.out);


    public static String next() throws IOException {
        String s = br.readLine();
        return s;
    }

    public static int nextInt() throws NumberFormatException, IOException {
        int n = Integer.parseInt(next());
        return n;
    }

    public static long nextLong() throws NumberFormatException, IOException {
        long n = Long.parseLong(next());
        return n;
    }

    public static double nextDouble() throws NumberFormatException, IOException {
        double n = Double.parseDouble(next());
        return n;
    }

    public static char nextChar() throws NumberFormatException, IOException {
        String s = next();
        char c = s.charAt(0);
        return c;
    }

    public static int[] nextIntArray() throws NumberFormatException, IOException {
        String[] s = next().split(" ");
        int size=s.length;
        int[] a = new int[size];
        for (int i = 0; i < size; i++) {
            a[i]=Integer.parseInt(s[i]);
        }
        return a;
    }
    public static long[] nextLongArray() throws NumberFormatException, IOException {
        String[] s = next().split(" ");
        int size=s.length;
        long[] a = new long[size];
        for (int i = 0; i < size; i++) {
            a[i]=Long.parseLong(s[i]);
        }
        return a;
    }
    public static double[] nextDoubleArray() throws NumberFormatException, IOException {
        String[] s = next().split(" ");
        int size=s.length;
        double[] a = new double[size];
        for (int i = 0; i < size; i++) {
            a[i]=Double.parseDouble(s[i]);
        }
        return a;
    }




    public void print(int n){out.print(n);}
    public void print(long n){out.print(n);}
    public void print(float n){out.print(n);}
    public void print(double n){out.print(n);}
    public void print(char n){out.print(n);}
    public void print(String n){out.print(n);}
    public void print(boolean n){out.print(n);}
    public void print(Object n){out.print(n);}
    public void print(char[] c){out.print(c);}
    public void print(int[] a){
        for (int i = 0; i < a.length; i++) {
            if(i!=(a.length-1))out.print(a[i]+" ");
            else out.println(a[i]);
        }
    }
    public void print(long[] a){
        for (int i = 0; i < a.length; i++) {
            if(i!=(a.length-1))out.print(a[i]+" ");
            else out.println(a[i]);
        }
    }
    public void print(double[] a){
        for (int i = 0; i < a.length; i++) {
            if(i!=(a.length-1))out.print(a[i]+" ");
            else out.println(a[i]);
        }
    }
    public void print(String[] a){
        for (int i = 0; i < a.length; i++) {
            if(i!=(a.length-1))out.print(a[i]+" ");
            else out.println(a[i]);
        }
    }



    public void println(){out.println();}
    public void println(int s){out.println(s);}
    public void println(long s){out.println(s);}
    public void println(float s){out.println(s);}
    public void println(double s){out.println(s);}
    public void println(char s){out.println(s);}
    public void println(String s){out.println(s);}
    public void println(boolean s){out.println(s);}
    public void println(Object s){out.println(s);}
    public void println(char[] s){out.println(s);}
    public void println(int[] a){
        for (int i = 0; i < a.length; i++) {
            out.println(a[i]);
        }
    }
    public void println(long[] a){
        for (int i = 0; i < a.length; i++) {
            out.println(a[i]);
        }
    }
    public void println(double[] a){
        for (int i = 0; i < a.length; i++) {
            out.println(a[i]);
        }
    }
    public void println(String[] a){
        for (int i = 0; i < a.length; i++) {
            out.println(a[i]);
        }
    }
    public void println(int[][] c){
        for (int i = 0; i < c.length; i++) {
            for (int j = 0; j < c[0].length; j++) {
                print(c[i][j] + " ");
            }
            println();
        }
    }
    public void println(long[][] c){
        for (int i = 0; i < c.length; i++) {
            for (int j = 0; j < c[0].length; j++) {
                print(c[i][j] + " ");
            }
            println();
        }
    }
    public void println(double[][] c){
        for (int i = 0; i < c.length; i++) {
            for (int j = 0; j < c[0].length; j++) {
                print(c[i][j] + " ");
            }
            println();
        }
    }
    public void println(char[][] c){
        for (int i = 0; i < c.length; i++) {
            for (int j = 0; j < c[0].length; j++) {
                print(c[i][j] + " ");
            }
            println();
        }
    }
    public void println(boolean[][] c){
        for (int i = 0; i < c.length; i++) {
            for (int j = 0; j < c[0].length; j++) {
                print(c[i][j] + " ");
            }
            println();
        }
    }


    public void flush(){out.flush();};
    public void close(){out.close();};
}