Tri-XOR

Time limit: 0.2s Memory limit: 64MB Input: tri-xor.in Output: tri-xor.out

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 TT zile, câte o pereche de două numere naturale AA și BB, A<BA < B. Pentru protecție maximă, antreprenorul trebuie să găsească suma „tri-xor” a unei perechi de numere incluse în intervalul [A,B][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:

trit 0 1 2
0 0 1 2
1 1 2 0
2 2 0 1

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 TT perechi de forma (A,B)(A, B), suma „tri-xor” maximă, ce se poate obține folosind două numere din intervalul [A,B][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 TT de teste.
Pe următoarele TT linii se vor găsi câte 2 numere, AA și BB, separate printr-un spațiu.

Date de ieșire

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

Restricții și precizări

  • 1T100 0001 \leq T \leq 100 \ 000;
  • 0A,B10180 \leq A, B \leq 10^{18} ;
# Punctaj Restricții
1 30 T,A,B100 T, A, B \leq 100
2 40 T,A,B1 000 T, A, B \leq 1 \ 000
3 30 Fără restricții suplimentare

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

  • 1515 „tri-xor” 17=2317 = 23
  • 99 „tri-xor” 9=189 = 18
  • 3737 „tri-xor” 37=7437 = 74
  • 7474 „tri-xor” 168=242168 = 242
  • 10011001 „tri-xor” 1005=20061005 = 2006

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

Log in or sign up to be able to send submissions!