Fişierul intrare/ieşire:	hansha.in, hansha.out	Sursă	Algoritmiada 2017 Runda 2
Autor	Eugenie Daniel Posdarascu	Adăugată de	Eugenie Daniel Posdarascu •eudanip
Timp execuţie pe test	0.35 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Hansha

Dupa numeroasele probleme cu palindromuri pe care le-a compus Dani, colegii sai de echipa i-au spus sa-si mai improspateze ideile, fiindca toata lumea s-a plictisit de ele. Dani a fost de-acord, dar n-a renuntat la pasiunea sa mai generala pentru simetrie. De aceasta data, el s-a inspirat din istoria imperiului antic Hansha, a carui dezvoltare i s-a parut foarte interesanta. Initial, imperiul Hansha era constituit dintr-un singur oras, iar acesta avea un numar pe post de nume: numarul 1. Apoi, in fiecare secol, timp de K secole, imperiul s-a dezvoltat astfel: Numarul sau de orase s-a dublat, iar daca orasele sale erau numerotate pana acum cu valori de la 1 la N, noile orase vor lua drept nume valorile N + 1, N + 2... 2 * N. Mai mult, aceste N noi orase vor avea exact aceeasi structura de drumuri ca orasele initiale. Mai exact, va exista drum intre orasul N + i si orasul N + j, unde 1 ≤ i, j ≤ N daca si numai daca exista deja un drum intre orasele i si j. Astfel, se poate spune ca in acest moment al fazei de dezoltare, imperiul s-a "oglindit", formand doua copii identice. Pentru a conecta aceste copii, se va mai construi un singur nou drum care va conecta un oras duplicat de corespondentul sau. Mai exact, pentru un unic 1 ≤ x ≤ N, se va adauga un drum intre nodurile x si N + x. Acest x poate varia de la o faza de dezvoltare la alta.

Dani are in fata mai multe scenarii posibile ale dezvoltarii imperiului Hansha. Un scenariu este definit printr-un numar K, care reprezinta numarul de faze de dezvoltare si descrierea celor K valori x, numerele oraselor care vor fi conectate cu duplicatul lor la fiecare dintre cele K faze ale dezvoltarii. Pentru fiecare scenariu, Dani va intreaba care este numarul minim de drumuri pe care trebuie sa-l parcurga pentru a ajunge din orasul A in orasul B dupa ce s-au finalizat toate etapele de dezvoltare in scenariul respectiv.

Date de intrare

Fişierul de intrare hansha.in va contine pe prima sa linie, valoarea T, reprezentand numarul de scenarii ce vor fi analizate. Urmeaza cele T scenarii, formatul unui scenariu fiind urmatorul: Pe prima linie se afla valoarea K, reprezentand numarul de faze de dezvoltare din scenariul respectiv. Urmeaza o linie cu K valori, reprezentand numarul orasului ce va fi conectat cu duplicatul sau in fiecare faza de dezvoltare. A treia linie va contine doua valori A si B, reprezentand numerele oraselor de a caror distanta este interesat Dani.

Date de ieşire

În fişierul de ieşire hansha.out se vor afla T valori, a i-a dintre acestea reprezentand raspunsul pentru intrebarea lui Dani din scenariul cu numarul i.

Restricţii

• 1 ≤ T ≤ 1.000
• 1 ≤ K ≤ 30
• Pentru 40 de puncte 1 ≤ K ≤ 10

Exemplu

Cum se trimit solutii?