Ai un prieten care ia momentan un curs de Automate Finite si vorbeste intr-una despre asta. Multa vreme ai crezut ca nu e un curs foarte legitim, fiindca prietenul tau vorbea despre automate care "tolereaza" cuvinte, pe cand stim cu totii ca formularea consacrata este "accepta". Astazi insa, prietenul tau ti-a definit mai exact "toleranta" si, ce-i drept, e relativ interesant.

Spunem ca un Auotomat Finit Determinist (prescurtat AFD) *tolereaza* stringul $X$ daca si numai daca exista un string $Y$ astfel incat $X$ este subsir de-al lui $Y$, iar $Y$ este acceptat de AFD in sensul clasic.

Spunem ca un 'Automat Finit Determinist':https://en.wikipedia.org/wiki/Deterministic_finite_automaton (prescurtat AFD) *tolereaza* stringul $X$ daca si numai daca exista un string $Y$ astfel incat $X$ este subsir de-al lui $Y$, iar $Y$ este acceptat de AFD in sensul clasic.

Dandu-ti-se un AFD esti curios cat de densa este multimea stringurilor tolerate de acesta relativ la multimea tuturor stringurilor peste alfabetul automatului. Mai formal, esti curios daca limita raportului dintre numarul de stringuri tolerate si numarul total de stringuri posibile atunci cand lungimea acestora tinde la infinit este strict pozitiva.

Dandu-ti-se un AFD esti curios cat de densa este multimea stringurilor tolerate de acesta relativ la multimea tuturor stringurilor peste alfabetul automatului. Mai formal, esti curios daca limita raportului dintre numarul de stringuri tolerate si numarul total de stringuri posibile (care, pentru o anumita lungime fixa $L$, sunt in numar de $SIGMA^L^$) cand lungimea acestora tinde la infinit este strict pozitiva.

h2. Date de intrare

* $1 ≤ T ≤ 100$
* $1 ≤ N ≤ 10.000$

* $1 ≤ K ≤ 26$

* $1 ≤ SIGMA ≤ 26$

* Starea de inceput este tot timpul starea cu numarul $1$.

* Pentru $90$ de teste $1 ≤ N ≤ 1.000$.

h2. Exemplu