In a popular computer game, Game of Palindromes also known as GOP there is a city called Palindesh. This city is unique in all possible ways. Like, a citizen of the Palindesh is considered to be luckier than the other citizens if he has a name with higher Lannister Ratio.
Lannister Ratio = (No. of Palindromic Substrings) / (No. of Total Substrings)
Your task is simple, a string of English alphabets are given. You have to find the Lannister Ratio.
A substring is a contiguous sequence of characters within a string. For instance, "the best of" is a substring of "It was the best of times". This is not to be confused with subsequence, which is a generalization of substring. For example, "Itwastimes" is a subsequence of "It was the best of times", but not a substring.
A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as madam or racecar or the number 10801.
[From Wikipedia]
Thus, a palindromic substring is a substring which is a palindrome.
Input
The first line contains a value $n$ ($1 \le n \le 100$), the number of total test cases that follows it. Each test case contains a string $S_i$ ($1 \le \texttt{Length of S} \le 1000$) consisting of only lower case English alphabets.
Output
Print $n$ lines, each line will be the Lannister Ratio of $S_i$. For simplicity print only 3 digits after the decimal point.
Sample
| Input | Output |
|---|---|
3 aa aba d | 1.000 0.667 1.000 |
