Fişierul intrare/ieşire:	lru.in, lru.out	Sursă	Lot Baia Mare 2013 - Baraj 2 Seniori
Autor	Adrian Panaete, Alexandru Cazacu	Adăugată de	Daniel Constantin Anghel •Magnvs
Timp execuţie pe test	0.2 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Lru

Adrian Wonder Boy tocmai a primit un joc nou. Acesta constă din n triunghiuri echilaterale situate în plan vertical având o latură orizontală şi vârful opus acesteia îndreptat în sus. Triunghiurile au laturile de lungime 1, 2, 3, …, n şi sunt incluse unul în altul astfel încât oricare două triunghiuri consecutive au un unghi comun. Mai precis, un triunghi mic (de latură i; în desen i=3) poate fi în exact urmatoarele 3 poziţii faţă de triunghiul mai mare (de latură i+1) :


`L.` triunghiul mic este “în stânga”.	`R.` triunghiul mic este “în dreapta”.	`U.` triunghiul mic este “sus”.

Starea jocului la un moment dat poate fi codificată printr-un şir de n-1 caractere ‘L’ , ‘R’ sau ‘U’ care descriu poziţia fiecărui triunghi de latura i (1<=i<n) faţă de triunghiul de latură i+1. De exemplu pentru n=4 în figurile de mai jos avem trei stări ale jocului împreună cu codificările acestora.


Starea 1: `RLL`	Starea 2: `RLU`	Starea 3: `LRU`

Starea jocului poate fi modificată prin glisarea unuia dintre triunghiurile interioare pe direcţia uneia dintre laturi într-un sens sau altul, cu exact o unitate. De exemplu glisând orizontal spre dreapta triunghiul de latură 2 se poate trece din starea 2 în starea 3. Faţă de triunghiul de latură 3, triunghiul de latură 2 a trecut din stânga în dreapta. (Reţineţi faptul că prin glisarea unui triunghi cele interioare lui rămân pe poziţia veche, deci unele mutări nu sunt posibile. De exemplu, în starea 1 triunghiul de latură 2 nu poate glisa în sus deoarece triunghiul de latură 1 ar rămâne în afara triunghiului de latură 2)

Pentru mai multe teste, cunoscând n şi două stări ale jocului, să se determine numărul minim de glisări în urma cărora jocul trece din prima stare în a doua stare.

Date de intrare

Pe prima linie a fişierului lru.in avem un număr natural t - numărul de teste. Următoarele 3*t linii descriu cele t teste, un test pe câte 3 linii. Prima linie dintre cele 3 conţine un număr natural n – lungimea comună a codificării celor două stări. A doua linie dintre cele 3 conţine un şir de n caractere – codificarea stării iniţiale. A treia linie dintre cele 3 conţine un sir de n caractere – codificarea stării finale.