Zadanie

Heavy-Light Decomposition

Počet bodov: 40, časový limit: 500ms

Keď ste upratovali pivnicu, našli ste pod hromadou prachu a zaváraninových pohárov aj nádhernú fotografiu holokarstu a vcelku zachovaný binárny strom. Stromček sa vám naozaj páči, každý vrchol má na sebe totiž napísané dve čísla a celý strom je generovaný iba dvoma jednoduchými pravidlami - ak má vrchol na sebe napísané čísla \(A\) a \(B\) tak:

1. ak je A=B tak je vrchol list
2. inak má jeho ľavý syn napísané čísla \(A\) a \((A+B)/2\) a jeho pravý syn \((A+B)/2+1\) a \(B\)

List nazveme osamelým, ak nie sú obaja synovia jeho otca listy. Viete čo máte robiť – spočítajte ich.

Vstup a výstup

Na prvom riadku je jedno celé číslo \(T\) - počet otázok.

Nasleduje \(T\) riadkov. Na \(i\)-tom riadku sú dve celé čísla \(A_i\) a \(B_i\), udavajúce dve čísla napísané v koreni stromu pre \(i\)-tu otázku.

Na výstup vypíšte \(T\) riadkov, pričom na \(i\)-tom riadku bude jedno celé číslo - odpoveď na \(i\)-tu otázku.

Obmedzenia

Vo všetkých testovacích sadách bude platiť \(0 \leq T \leq 10^5\) a \(0 \leq N \leq 10^{18}\), pričom \(0 \leq A_i \leq B_i \leq N\) pre všetky \(i\). Navyše, obmedzenia na N a T budú v jednotlivých sadách nasledovné:

|   \logT|2|3|4|5|
|logN\   +-+-+-+-|
|    2   |X| | |X|
|    4   | |X| |X|
|    7   | | |X|X|
|   18   |X|X|X|X|

kde X reprezentuje existenciu jednej sady s danými obmedzeniami (teda napríklad posledný riadkok a stĺpec znamená sadu s \(T=10^5, N=10^{18}\)). Bude teda 10 sád, za každú sadu získate 10% celkového počtu bodov.

Upozorňujeme, že vstupné súbory môžu byť vcelku masívne a preto odporúčame použiť rýchle načítavanie a vypisovanie vo vami zvolenom jazyku.

Príklady

Input:

2
2 4
4 5

Output:

1
0

(2,4) -> (2,3),(4,4); (2,3) -> (2,2), (3,3). (4,4) je jediný osamelý list.