A foreign restaurant recently opened in your area. You like the food they make, so you convinced your friends to start having lunch there each day. But all the dishes have foreign names and you don’t know which is which. You can only identify a dish after you order it.
There are p people in your group (including yourself) and the restaurant serves d different dishes. Ordering at the restaurant works as follows: First, each person orders exactly one dish by specifying a number between 1 and d. Then, the p dishes ordered by the group are brought to the table all at once, in no particular order and with no information on which is which.
Your goal is to create a menu in your language: you want to map all numbers between 1 and d to names of dishes in your language. Assuming that your friends are willing to cooperate, what is the smallest number of lunches in which this can be done?
Find the smallest number of lunches ℓ such that there is a strategy for placing the orders in such a way that after ℓ lunches you will know the names of all dishes. In the hard subproblem L2, you also have to find the number of valid first day orders.
An order is a multiset of dish numbers your group ordered. For example, if p = 3 and d = 2, the order {1, 1, 2} is the same as the order {2, 1, 1} but different from the order {1, 2, 2}. A valid first day order is an order such that if your group makes the order on the first day, there will be a strategy that solves our task by making ℓ − 1 additional orders.
The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line. Each test case consists of a single line containing the numbers p and d.
In the easy subproblem L1 we have t = 81, 1 ≤ p ≤ 9, and 1 ≤ d ≤ 9.
In the hard subproblem L2 we have t = 320, 1 ≤ p ≤ 16, and 1 ≤ d ≤ 20.
Output a single line for each test case.
In the easy subproblem L1 the line should contain a single integer: the minimum number of days.
In the hard subproblem L2 the line should contain two integers: the minimum number of days, and the number of valid first day orders.
Input:
3
1 1
2 3
6 3Output:
1 1
2 3
1 6In the first example, note that the answer is not 0: you have to order the dish once to see what it is.
Here’s one optimal strategy for p = 2 and d = 3: On the first day, one of you will order dish 1 and the other will order dish 2. On the second day, order dishes 1 and 3.
In the third example order one dish 1, two dishes 2, and three dishes 3.