Mirror - Future for Future IX - 2024 | Tri-XOR

Constănțeanu' s-a îmbogățit în urma construirii hotelului din Bansko. Trăiască liceele din Constanța! Acum, însă, lumea rea caută să îi fure averea. Pentru a-i opri, acesta își schimbă parola zilnic la contul bancar. Banca Dobrogeana îi trimite de-a lungul a $T$ zile, câte o pereche de două numere naturale $A$ și $B$, $A < B$. Pentru protecție maximă, antreprenorul trebuie să găsească suma „tri-xor” a unei perechi de numere incluse în intervalul $[A,B]$.

Operația „tri-xor” este analoagă operației „xor”, însă se aplică pe scrierea numerelor în baza 3 pe „triți” (cifrele numărului în baza 3) aflați pe aceleași nivel, iar tabelul de valori este următorul:

Spre exemplu, 15(0120) „tri-xor” 30(1010) = 36(1100) sau 2(0002) „tri-xor” 2(0002) = 1(0001).

Cerință

Ajutați-l pe Constănțeanu' să gasească pentru fiecare din cele $T$ perechi de forma $(A, B)$, suma „tri-xor” maximă, ce se poate obține folosind două numere din intervalul $[A,B]$. Cine știe? Poate vă alegeți cu o cameră cu vedere la pârtie!

Date de intrare

Pe primia linie a fișierului de intrare tri-xor.in se va găsi numărul $T$ de teste.
Pe următoarele $T$ linii se vor găsi câte 2 numere, $A$ și $B$, separate printr-un spațiu.

Date de ieșire

Se vor afișa $T$ numere, fiecare pe câte o linie a fișierului tri-xor.out, astfel pe linia $i$ aflându-se răspunsul la a $i$-a întrebare.

Restricții și precizări

• $1 \leq T \leq 100 \ 000$;
• $0 \leq A, B \leq 10^{18}$;

Exemplu

tri-xor.in

5
15 26
1 9
2 37
45 168
0 1005

tri-xor.out

23
18
74
242
2006

Explicație

• $15$ „tri-xor” $17 = 23$
• $9$ „tri-xor” $9 = 18$
• $37$ „tri-xor” $37 = 74$
• $74$ „tri-xor” $168 = 242$
• $1001$ „tri-xor” $1005 = 2006$

Toate aceste soluții sunt maxime, dar nu neapărat unice.