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

Pentru orice permutare de n elemente putem determina un sir de n-1 relatii (relatiile folosite fiind < sau >). Daca al i-lea element al permutarii este mai mic decat al i+1-lea element, al i-lea element al sirului de relatii va fi <, in caz contrar, al i-lea element al sirului de relatii va fi >. De exemplu pentru permutarea (1,3,2,4) de patru elemente determinam sirul (<, >, <). Va trebui sa determinati cate permutari de n elemente exista carora le corespunde un anumit sir de relatii. Ne intereseaza doar restul impartirii acestui numar la 29997.

Pentru orice permutare de $N$ elemente putem determina un sir de $N-1$ relatii (relatiile folosite fiind $<$ sau $>$). Daca al $i$-lea element al permutarii este mai mic decat al $i+1$-lea element, al $i$-lea element al sirului de relatii va fi $<$, in caz contrar, al $i$-lea element al sirului de relatii va fi $>$. De exemplu pentru permutarea $(1,3,2,4)$ de patru elemente determinam sirul $(<, >, <)$. Va trebui sa determinati cate permutari de $N$ elemente exista carora le corespunde un anumit sir de relatii. Ne intereseaza doar restul impartirii acestui numar la $29997$.

h2. Date de intrare

Pe prima linie a fisierului doipe.in se va afla numarul t semnificand numarul testelor din fisier. Pe urmatoarele 2*t linii se vor afla informatii despre fiecare test. Astfel pe linia 2*k (1≤k≤t) se va alfa numarul n, iar pe linia 2*k+1 (1≤k≤t), sirul de relatii.

Pe prima linie a fisierului $doipe.in$ se va afla numarul $T$ semnificand numarul testelor din fisier. Pe urmatoarele $2*T$ linii se vor afla informatii despre fiecare test. Astfel pe linia $2*k$ ($1≤k≤T$) se va alfa numarul $N$, iar pe linia $2*k+1$ ($1≤k≤T$), sirul de relatii.

h2. Date de iesire

Fisierul doipe.out  va trebui sa contina exact t linii. Pe a i-a linie va trebui sa se afle raspunsul pentru al i-lea test din fisierul de intrare.

Fisierul $doipe.out$  va trebui sa contina exact $T$ linii. Pe a $i$-a linie va trebui sa se afle raspunsul pentru al $i$-lea test din fisierul de intrare.

h2. Restrictii

* 1 ≤ t ≤ 20
* 1 ≤ n ≤ 2000
* 40% din fisierele de test vor avea toate valorile lui n mai mici sau egale cu 16
* 70% din fisierele de test vor avea toate valorile lui n mai mici sau egale cu 2000

* $1 ≤ t ≤ 20$
* $1 ≤ n ≤ 2.000$
* $40% din fisierele de test vor avea toate valorile lui n mai mici sau egale cu 16$
* $70% din fisierele de test vor avea toate valorile lui n mai mici sau egale cu 200$

h2. Exemplu