h2. Date de intrare

Fişierul de intrare $eqprob.in$ va contine pe prima linie un numar intreg $T$ reprezentand numarul de teste. Fiecare test are urmatorul format: pe prima linie se afla un numar intreg $N$, lungimea sirului; pe a doua linie se afla sirul $S$.

Fişierul de intrare $eqprob.in$ va contine pe prima linie $N$, lungimea sirului. Pe a doua linie se afla sirul $S$.

h2. Date de ieşire

În fişierul de ieşire $eqprob.out$ se vor afla raspunsurile pentru cele $T$ teste. Raspunsul pentru fiecare test are urmatorul format: un numar real reprezentand probabilitatea ca $A$ si $B$ sa fie egale, afisata cu o precizie de *12 zecimale*.

În fişierul de ieşire $eqprob.out$ se va afla probabilitatea ca $A$ si $B$ sa fie egale, afisata cu o precizie de *12 zecimale*.

h2. Restricţii

* $1 ≤ T ≤ 10$

* $1 ≤ N ≤ 50$
* $S$ contine doar litere mici ale alfabetului englez.
* Se numeste subsir de lungime $K$ al sirului $S$ un sir $T = S[~i1~]S[~i2~]...S[~iK~]$, astfel incat $1 &le; i[~1~] < i[~2~] < ... < i[~K~] &le; N$.

h2. Exemplu
table(example). |_. eqprob.in |_. eqprob.out |

|3
1

|1

x

2

|1.000000000000
|
|2

aa

3

|0.555555555556
|
|3

aca

|1.000000000000
0.555555555556
0.190476190476

|0.190476190476

|
h3. Explicaţie

In testul 2, $S = aa$.
 

In exemplul 2, $S = aa$.

Exista $3$ subsiruri nevide: $a, a, aa$.
Exista $3$ subsecvente nevide: $a, a, aa$.

Deci, probabilitatea totala este $1/3 * 2/3 + 1/3 * 2/3 + 1/3 * 1/3 = 5/9$.

== include(page="template/taskfooter" task_id="eqprob") ==

== include(page="template/taskfooter" task_id="eqprob") ==