== include(page="template/taskheader" task_id="sieve") ==

//Povestea va fi schimbata

Esti acasa (afara fie e prea cald, fie e prea frig) si citesti problema 'Ciurulet':problema/ciurulet. Te intrebi: oare in cate feluri pot gresi Algoritmul lui Eratosthene astfel incat comportamentul lui sa fie semi-interesant?

In aceasta problema vom analiza cum se comporta Ciurul lui Eratosthene daca in loc sa parcurgem numerele in ordinea {2, 3, 4, .. N}, le parcurgem in ordinea data de o permutare aleatoare a acestor numere. Mai exact, dandu-se acest pseudocod:

Raspunsul pare sa fie "suficiente".
 
In aceasta problema vei analiza cum se comporta Ciurul lui Eratosthene daca in loc sa parcurgi numerele in ordinea ${2, 3, 4, .. N}$, le parcurgi in ordinea data de o permutare aleatoare a acestor numere. Mai exact, dandu-se acest pseudocod:

== code(c) |
int countSteps(int n, vector<int> p) {

//identity are valoarea 4, iar misplaced_four are valoarea 5.
==

 
 
Ne intrebam care este valoarea medie intoarsa de functia $countSteps()$ daca permutarea $p$ este generata aleator si uniform.

Dandu-ti-se un numar $N$, te intrebi care este valoarea medie asteptata intoarsa de functia $countSteps(N, p)$ daca permutarea $p$ este generata aleator si uniform. Daca nu stii ce inseamna valoare medie (ceea ce ar fi ciudat, fiindca ti-ai pus singur intrebarea), sa stii ca este numarul obtinut prin calcularea mediei aritmetice a tuturor rezultatelor functiei atunci cand o executi pe toate permutarile posibile.

h2. Date de intrare

Fişierul de intrare $sieve.in$ ...

Fişierul de intrare $sieve.in$ va contine pe prima sa linie numarul $T$ reprezentand numarul de teste. Urmatoarele $T$ teste contin cate o valoare $N$.

h2. Date de ieşire

În fişierul de ieşire $sieve.out$ ...

În fişierul de ieşire $sieve.out$ se vor afla $T$ linii, fiecare continand cate un numar real, reprezentand raspunsul pentru testul corespunzator.

h2. Restricţii

* $1 ≤ N ≤ 100.000$

* $1 ≤ T ≤ 100.000$

* $2 ≤ N ≤ 100.000$
* Un raspuns este considerat corect daca diferenta absoluta dintre acesta si raspunsul corect este mai mica sau egala cu $10^-4^$.

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

| 1

| 2
9

250

| 577.8554834

| 5.5
577.8554834

|
== include(page="template/taskfooter" task_id="sieve") ==