Welcome to ZOJ Problem Sets Information Select Problem Runs Ranklist ZOJ Problem Set - 4047
Live Love

Time Limit: 1 Second      Memory Limit: 65536 KB

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, \dots, A_n$ ($A_i \in$ {PERFECT, NON-PERFECT}). The score of the song is equal to the \textit{max-combo} of the result sequence, which is defined as the maximum number of continuous PERFECTs in the sequence.

Formally speaking, $\text{max-combo}(A) = \max$ {$k$ | $k$ is an integer and there exists an integer $i$ ($1 \le i \le n-k+1$) such that $A_i = A_{i+1} = A_{i+2} = \dots = A_{i+k-1} =$ PERFECT}. For completeness, we define max($\emptyset$) = 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 $\text{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 \le T \le 100$), indicating the number of test cases. For each test case:

The only line contains two integers $n$ and $m$ ($1 \le n \le 10^3$, $0 \le m \le 10^3$, $m \le 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.

Author: CHEN, Shihan
Source: The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online
Submit    Status