Problem Specification

Bob is the best student in his class, which means he often gets bored when teachers drone on and on about something he already knows everything about.
His favorite topic is probability and he often challenges himself by creating new questions and games based on probability.
Today he wants to find the probability that on choosing a random substring P of length k from a string S, it is a palindrome.

Palindromes of length k are different if they start from different positions.

Input Specification

The first line of the input file contains t representing the number of test cases. Each test case contains 2 lines of input, the first line specifying k and the next representing the string S.

1<= Length of String S <=3000
1<= t <=100

Output Specification

There is one line of output for each test case. This is the probability,upto 4 places of decimal, that the on choosing a substring of length k from S it will be a palindrome.

Sample Input

``` 2 3 aaaa 4 abbaab ```

Sample Output

``` 1.0000 0.6667 ```

Note : Letters are not case sensitive. k will always be less than or equal to the length of S.

Problem Setter : Neesha Sinha

Languages: C,C++,C#,Java,JavaScript,Pascal,Perl,PHP,Python,Ruby

Time Limit: 3 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0