Let us define the cost of a string S as the length of the longest substring of S which has all the characters same. For example, the cost of string abaaaba is 3, and the cost of string abcd is 1.

You found a new language L containing c distinct characters. Language L contains only all strings of length n which can be formed from these c characters. Now, you choose a string at random from these \(c ^ n\) strings. Find the expected value of the cost of this string.

You will be given T test cases, each containing c and n. Your answer is considered correct if the absolute OR relative error between the actual answer and your answer is \( \lt 10^{-6} \)

Input

The first line contains T, the number of test cases.
\(i^{\text{th} } \) of the next T lines contain two integers, c and n, the number of distinct characters, and the length of strings in L respectively.

Output
Print T lines . The \(i^{\text{th} }\) line should contain the answer to the \(i^{\text{th}}\) test case

Constraints

\(1 \le T \le 50\)
\(1 \le c, n \le 10^9 \)