lru

Cerință

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,\dots,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$):

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$ 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 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 \cdot 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.

Date de ieșire

Fișierului lru.out va conţine $t$ linii. Linia $k \ (1 \leq k \leq t)$ va conţine un număr natural $m_k$ – soluţia testului $k$ din fişierul de intrare.

Restricții și precizări

• $1 \leq t \leq 5$
• $2 \leq n \leq 1 \ 000 \ 000$
• Pentru $70\%$ din teste, $n \leq 200 \ 000$

Exemplu

lru.in

1
3
RLL
LRU

lru.out

5

Explicație

Se efectuează $5$ glisări și jocul trece prin următoarele stări:
RLL $\rightarrow$ ULL $\rightarrow$ LUL $\rightarrow$ RUL $\rightarrow$ RLU $\rightarrow$ LRU