I have bought n chocolates for my young cousins. Every chocolate is different. So, in the contest I added the problem that how many ways I can distribute the chocolates to my K cousins. I can give more chocolates to some cousins, and may give no chocolate to some. For example, I have three cousins and I bought 2 chocolates a and b. Then I can distribute them in the following 9 ways:
| # | Cousin 1 | Cousin 2 | Cousin 3 |
|---|---|---|---|
| 1 | a, b | ||
| 2 | a, b | ||
| 3 | a, b | ||
| 4 | a | b | |
| 5 | a | b | |
| 6 | a | b | |
| 7 | b | a | |
| 8 | b | a | |
| 9 | b | a |
As the result can be large, I asked for the result modulo 100 000 007 (a prime). But after that I found that this problem is easier than I thought. So, I changed the problem a little bit. I will give you the number of my cousins K and the result modulo 100000007 (108 + 7). Your task is to find the number of chocolates I have bought. If there are several solutions, you have to find the minimum one.
Input
Input starts with an integer T (≤ 1000), denoting the number of test cases.
Each case starts with a line containing two integers K (2 ≤ K ≤ 107) and result (0 ≤ result < 100000007). You can assume that the input data is valid, that means a solution exists.
Output
For each case, print the case number and the minimum possible number of chocolates I have bought.
Sample
| Sample Input | Sample Output |
|---|---|
2 3 9 2 100 | Case 1: 2 Case 2: 23502611 |