4652：Dice

You have a dice with m faces, each face contains a distinct number. We assume when we tossing the dice, each face will occur randomly and uniformly. Now you have T query to answer, each query has one of the following form:
0 m n: ask for the expected number of tosses until the last n times results are all same.
1 m n: ask for the expected number of tosses until the last n consecutive results are pairwise different.

The first line contains a number T.(1≤T≤100) The next T line each line contains a query as we mentioned above. (1≤m,n≤10⁶) For second kind query, we guarantee n≤m. And in order to avoid potential precision issue, we guarantee the result for our query will not exceeding 10⁹ in this problem.

For each query, output the corresponding result. The answer will be considered correct if the absolute or relative error doesn't exceed 10^-6.