DreamGrid is playing the music game Live Love. He has just finished a song consisting of n notes and got a result sequence A​1​​,A​2​​,...,A​n​​ (A​i​​∈ {PERFECT, NON-PERFECT}). The score of the song is equal to the max-combo of the result sequence, which is defined as the maximum number of continuous PERFECTs in the sequence.

Formally speaking, max-combo(A)=max { k | k is an integer and there exists an integer i (1≤i≤n−k+1) such that A​i​​=A​i+1​​=A​i+2​​=...=A​i+k−1​​= PERFECT }. For completeness, we define max(∅)=0.

As DreamGrid is forgetful, he forgets the result sequence immediately after finishing the song. All he knows is the sequence length n and the total number of PERFECTs in the sequence, indicated by m. Any possible score s he may get must satisfy that there exists a sequence A​′​​ of length n containing exactly m PERFECTs and (n−m) NON-PERFECTs and max-combo(A​′​​)=s. Now he needs your help to find the maximum and minimum s among all possible scores.

Input

There are multiple test cases. The first line of the input contains an integer T (1≤T≤100), indicating the number of test cases. For each test case:

The only line contains two integers n and m (1≤n≤10​3​​, 0≤m≤10​3​​, m≤n), indicating the sequence length and the number of PERFECTs DreamGrid gets.

Output

For each test case output one line containing two integers s​max​​ and s​min​​, indicating the maximum and minimum possible score.

Sample Input

5

5 4

100 50

252 52

3 0

10 10

Sample Output

4 2

50 1

52 1

0 0

10 10

Hint

Let's indicate a PERFECT as P and a NON-PERFECT as N.

For the first sample test case, the sequence (P,P,P,P,N) leads to the maximum score and the sequence (P,P,N,P,P) leads to the minimum score.

题目意思：对于t组样例，每一组一共有n个音符，m个音符属于一种，剩下的音符都是不同种的，出现连续同一种音符的个数作为得分，求最大得分和最小得分。

解题思路：其实我们可以这样想一共会有x=n-m+1种音符，最大得分必然是相同音符的数量也就是m，而对于最小得分：如果音符的种类x大于等于同一种的数量m,

那么同一种音符便可以被不同种的音符一一分割开；如果音符的种类小于同一种的数量m,那么想要得到最小连续同一类的音符数，可以理解为将m利用不同种类的音符划分为若*分。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int main()

 {

     int t,a,b,ans,x;

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d%d",&a,&b);

         x=a-b+;

         if(b==)

         {

             ans=;

         }

         else if(x>=b)

         {

             ans=;

         }

         else if(x<b)

         {

             if(b%x!=)

             {

                 ans=b/x+;

             }

             else

             {

                 ans=b/x;

             }

         }

         printf("%d %d\n",b,ans);

     }

     return ;

 }