During the rare holiday, Xiao Bai's class organized a trip to the cinema. However, because there are so many people watching movies during the holiday, it is difficult for the whole class to watch the same movie. Finally, everyone found a cinema in a remote alley. This cinema has a very special way of assigning seats, as follows:

1. There are $K$ seats in the cinema, numbered $1 \dots K$. After each person buys a ticket, they are randomly assigned a seat. Specifically, a positive integer $L$ is chosen uniformly at random from $1 \dots K$.
2. If seat $L$ is empty, it is assigned to the person. Otherwise, $L$ is incremented by one, and the previous step is repeated.
3. If no seat with number $L$ exists in the second step, the person must stand to watch the movie, which is known as a standing ticket.

There are $N$ people in Xiao Bai's class (including Xiao Bai). As a math enthusiast, Xiao Bai wants to know the probability that everyone in the class can have a seat.

Input

The first line of the input file contains a single positive integer $T$, representing the number of test cases. The next $T$ lines each contain two positive integers $N$ and $K$, separated by a single space, with the same meanings as described in the problem.

Output

The output file contains $T$ lines. The $i$-th line should contain two space-separated integers $A$ and $B$, representing the answer for the $i$-th test case as the fraction $A/B$. (Note: The answer must be expressed as an irreducible fraction.)

Constraints

For 20% of the data: $N, K \le 10$ For 100% of the data: $T \le 50, N, K \le 200$

Examples

Input 1

3
1 1
2 1
2 2

Output 1

1 1
0 1
3 4