The night before the final contest METU CClub runs Wheel of Fortune show to cheer up contestants. Now it's your time to play. The wheel is divided by \(N\) sections numbered from 1 to \(N\) clockwise. Each of the sections contains a letter. We'll denote them with \(S_1, S_2, ... , S_N\) correspondingly.

First, the organizers put a bandage on your eyes so you can not see the wheel anymore. Then you spin the wheel to determine the first section and spin it again to determine the second section. Starting from the first section and moving clockwise to the second section the organizers write down the letters of a secret word. Further, they hide the word and take your eye bandage off. Now you have to guess the secret word!

You don't see hidden secret word however you see the wheel with letters. You can ask the organizers yes/no questions regarding the word. What is the minimum expected number of questions required to guess the secret word? Note that it's enough to guess the word, i.e. you don't have to guess the first and the second wheel sections.

Input

The first line contains integer \(N\). The second line contains \(N\) letters \((S_1, S_2, ... ,S_N)\).

Output

The minimum expected number of questions. An output is considered correct if its absolute or relative error does not exceed \(10^{−7}\).

Constraints

• \(1 ≤ N ≤ 1000\)
• \(S_1,S_2,...,S_N\) - lowercase letters ('a'-'z').

Examples

Input (stdin)

2
ab

3
xxx

Output(stdout)

2.0
1.66666666667

Notes

In the first sample there are 4 possible words: a, b, ab, ba. Each of them can be the secret word with the same probability \(1/4\). One of the optimal game strategies is the following:

• Ask if the secret word starts with letter 'a'?
• Ask if the secret word ends with letter 'a'?