# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Game of Palindromes

By ghazanfar · Limits 1s, 512 MB

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 sub strings) / (No. of total sub strings)
``````

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 sub string is a sub string which is palindrome.

## Input

The first line contains a value n, the number of total test cases followed by n (1 ≤ n ≤ 100) lines each containing a string Si (1 ≤ |S| ≤ 1000) consisting of only small case English alphabets.

## Output

Print n lines, each line will be the Lannister Ratio for Si for simplicity print only 3 digit after the decimal point.

## Sample

InputOutput
```3
aa
aba
d
```
```1.000
0.667
1.000
```

### Statistics

64% Solution Ratio

RAKIBULHOSSAINEarliest, May '19

Sobi777Fastest, 0.0s

bu_hridoyLightest, 131 kB

omar24Shortest, 498B