drei

Arheologii au descoperit, printre alte vestigii ale unei civilizaţii dispărute, o reprezentare neobișnuită a numerelor pe care au denumit-o DREI. În reprezentarea DREI apar semne care au fost echivalate de arheologi cu literele mici din alfabetul englez. O reprezentare DREI este un șir de litere distincte care fie constă dintr-o singură literă, fie respectă următoarele două condiţii:

1. litera maximă apare la unul dintre capete;
2. şirul obţinut prin eliminarea literei maxime este o reprezentare DREI.

Primele douăsprezece reprezentări, corespunzătoare numerelor $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$, $10$, $11$, $12$ sunt a, ab, b, ba, bac, bc, abc, ac, c, ca, cab, cb.

Să notăm cu $\text{max}(x)$ cea mai mare literă din reprezentarea DREI $x$.

Pentru a compara două reprezentări DREI notate cu $x$ şi respectiv $y$ aplicăm, în ordine, următoarele reguli:

1. Dacă $\text{max}(x) > \text{max}(y)$, atunci $x > y$.
2. Reprezentarea formată dintr-o singură literă este mai mare decât orice altă reprezentare care are aceeași literă maximă în capătul drept și este mai mică decât orice altă reprezentare care are aceeași literă maximă în capătul stâng.
3. Dacă ambele reprezentări $x$ și $y$ au aceeași literă maximă poziţionată la capătul drept, atunci se elimină litera maximă din ambele reprezentări și se compară reprezentările obţinute (să le notăm $x_{dr}$ și $y_{dr}$). Dacă $x_{dr} < y_{dr}$, atunci $x > y$, respectiv dacă $x_{dr} > y_{dr}$, atunci $x < y$.
4. Dacă ambele reprezentări $x$ și $y$ au aceeași literă maximă poziţionată la capătul stâng, atunci se elimină litera maximă din ambele și se compară reprezentările obţinute (să le notăm cu $x_{st}$ şi $y_{st}$). Dacă $x_{st} < y_{st}$, atunci $x < y$, respectiv dacă $x_{st} > y_{st}$, atunci $x > y$.

De exemplu:

• edabc $<$ edc (se aplică mai întâi regula 4, apoi se compară dabc cu dc; se aplică din nou regula 4 şi se compară abc cu c, apoi se aplică regula 2);
• ab $<$ b $<$ ba, conform regulii 2;
• abe $<$ caf, conform regulii 1;
• bac $<$ cba, conform regulii 2;
• bac $<$ abc (se aplică mai întâi regula 3, apoi se compară ba cu ab, aplicând regula 2).

Cerință

Scrieţi un program care să determine răspunsurile pentru $Q$ interogări de următoarele 4 tipuri:

Date de intrare

Fişierul de intrare drei.in conţine pe prima linie numărul natural $Q$ reprezentând numărul de interogări.

Pe următoarele $Q$ linii se află cele $Q$ interogări, câte o interogare pe o linie, în formatul descris mai sus.

Date de ieșire

Fişierul de ieşire drei.out va conţine $Q$ linii. Pe linia $i$ va fi scris răspunsul pentru cea de a $i$-a interogare din fișierul de intrare.

Restricții și precizări

• $1 \leq Q \leq 10^5$
• $1 \leq N \leq 10^{12}$
• Șirurile de caractere care apar în interogări au lungimea cel mult egală cu $26$.
• Reprezentările DREI sunt numerotate în ordine crescătoare începând cu $1$.

Exemplu

drei.in

6
1 acb
1 abcd
1 xabby
2 bac abc
3 12
4 cb

drei.out

0
1
0
-1
cb
12