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 cn 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 <10−6
Input
Output
Print T lines . The ith line should contain the answer to the ith test case
Constraints
1≤T≤50
1≤c,n≤109
In the first test case, c=2, n=3. Lets say the c distinct characters are 0,1. Then the strings are:
000
having cost 3001
having cost 2010
having cost 1011
having cost 2100
having cost 2101
having cost 1110
having cost 2111
having cost 3The expectation value of cost is 3+2+1+2+2+1+2+38=2
In the second test case, the probability that both characters of string are same is 13. So, the expectation value is 23×1+13×2=43