# Probability of Palindromes

**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