Zadanie

Cestovateľ Jožko

Počet bodov: 20, časový limit: 2000ms

Jožko sa s kamarátmi v lete chystá na turistiku do Novej Sedlice, najvýchodnejšej obce Slovenska, v okolí ktorej sa nachádza nespočetné množstvo prírodných krás. Vydajú sa tam už po tretíkrát v priebehu posledných troch rokov a zdržia sa tu niekoľko dní, avšak, ani tak sa im asi nepodarí navštíviť všetko zaujímavé v okolí našej východnej hranice.

Každý deň si spravia túru, ktorá vyzerá nasledovne: stopom pricestujú na nejaké zaujímavé miesto \(a\), tam si dajú obed, odkráčajú k zvolenej destinácií \(b\), kde si dajú olovrant, a následne sa stopom odvezú domov.

Nastáva však problém: ak destinácia nieje dostatočne zaujímavejšia od začiatočnej prírodnej krásy, chlapcom sa nebude chcieť kráčať. Ak je však destinácia príliš zaujímavá, už pri obzeraní prvej lokality budú mať na mysli len tú, a prvú lokalitu si naplno nevyužijú.

Jožko s kamarátmi teda každej lokalite priradili číslo určujúce zaujímavosť, a prišli na to, že z lokality s hodnotou \(a\) je ako destináciu vhodné vybrať lokalitu s hodnotou \(2a\), alebo \(2a+1\).

Ak si lokality popárujú optimálne, koľko najviac túr vedia spolu podniknúť?

Každú lokalitu samozrejme chcú navštíviť práve raz.

Úloha

Máme \(n\) lokalít, ktoré chceme navštíviť. Každému miestu \(i\) priradíme číslo \(a_i\), určujúce jej zaujímavosť. Dvojica \((a_i, a_k)\) je vhodná ak \(a_k = 2a_i\) alebo \(a_k = 2a_i +1\). Každé číslo môže byť vybrané do najviac jednej dvojice.

Zistite najväčší počet vhodných dvojíc, ktoré vieme popárovaním čísel dosiahnuť.

Vstup

V prvom riadku vstupu je číslo \(t\) udávajúce počet sád. Nasleduje \(t\) dvojíc riadkov. Na prvom z tejto dvojice sa nachádza číslo \(n\) označujúce počet lokalít. Na druhom sa nachádza \(n\) čísel \(1 \leq a \leq 10^{18}\).

Platí, že súčet všetkých \(n\) je najviac \(10^6\).

Výstup

Vypíšte najväčší počet platných dvojíc aké boli popísané vyššie.

Input:

4
2
1 2
3 
1 2 4
4
1 2 8 4
4
4 4 3 3

Output:

1
1
2
0