Description

During a rare holiday, Xiaobai’s (Xiaobai) class organizes a movie trip. However, because many people watch movies during holidays, it is hard to seat everyone in the same showing. Finally, they find a cinema in a remote alley, but its seating assignment is special, as follows:

The cinema has $K$ seats, labeled $1 \sim K$. After buying a ticket, each person is randomly assigned a seat. Specifically, an integer is chosen uniformly at random from $1 \sim K$, and let it be $L$.

If seat $L$ is empty, this seat is assigned to the person. Otherwise, increase $L$ by one and repeat the previous step; if there is no seat numbered $L$, then the person has to stand to watch the movie, i.e., a standing ticket.

There are $N$ people in Xiaobai’s class (including Xiaobai). As a math enthusiast, Xiaobai wants to know the probability that the whole class can get seats.

Input Format

Multiple test cases. The first line contains an integer $T$ denoting the number of test cases. Then each of the next $T$ lines contains two integers $N,K$ denoting the number of people and the number of seats in the cinema.

Output Format

For each test case, output two integers $A,B$ on one line, indicating that the answer is $\frac{A}{B}$. You need to ensure $\gcd(A,B) = 1$.

3
1 1
2 1
2 2

1 1
0 1
3 4

Hint

For $100 \%$ of the testdata, $1 \leq T \leq 50$, $1 \leq N,K \leq 200$.

Translated by ChatGPT 5