Energie

Undeva în munții Anzi este un străvechi templu Inca ce conține o cameră cu artefacte. Camera este protejată de un un câmp de energie, a cărei energie este reprezentată printr-un număr sacru $E$.
După lungi studii și călătorii, Dora Exploradora ajunge la intrarea în camera secretă și citind inscripțiile de pe pereții templului află că numărul sacru $E$ este cuprins între 1 și $n$, $n$ fiind de forma $2^{d}$, $d$>0. De asemenea Dora știe paritatea numărului inițial.
Mecanismul funcționează pe baza a două ritualuri:

• ritualul divizării care permite reducerea numărului la jumătate, doar dacă acesta este par
• ritualul domolirii care permite scăderea numărului cu 1, acesta poate fi activat oricând.

Mecansimul se va deschide odată ce valoarea numărului sacru este redusă la 0. După fiecare ritual în care templul sacru nu este deschis, acesta răspunde printr-un număr natural $x$ indicând că valoarea energiei curente este divizibilă cu $2^{x}$ dar nu cu $2^{x+1}$.
Dacă după $r$ ritualuri energia câmpului nu a fost redusă la 0, atunci templul nu mai poate fi deschis pentru următorii 100 de ani. Dacă templul este deschis, cel care îl deschide, poate seta valoarea urmatoarei energii.

Dora reusește să deschidă camera, dar, curioasă din fire se întreabă pentru câte valori distincte ale energiei inițiale, și aplicând ritualurile în mod optim, camera nu ar putea fi deschisă.

Cerință

Ajutați-o pe Dora să determine numărul valorilor $E$ $\in [1,n]$ pentru care energia camerei secrete nu ar putea fi redusă la 0 în r ritualuri.

Date de intrare

Fișierul energie.in conține pe prima linie un număr natural $Q$ reprezentând numărul de teste. Următoarele $Q$ linii conțin căte două perechi de valori $n$,$r$.

Date de ieșire

Fișierul de ieșire energie.out conține $n$ linii, fiecare linie $i$ conține numărul valorilor pe care le poate avea $E$ pentru testul $i$.

Restricții și precizări

• se garanteză că pentru toate datele de test valoarea lui n este o putere de 2
• $1 \leq n,r \leq 2^{30}$;
• $1 \leq Q \leq 10 \ 000$;
• pentru teste în valoare de 30 de puncte $1 \leq n,r \leq 2^{15}$

Exemplu

energie.in

5
4 1 
4 2
4 7
16 2
16 3

energie.out

3
2
0
14
12

Explicație

Pentru $n=4$ $r=1$ singura valoare a lui $E$ pentru care se poate deschide camera este 1. Pentru $E \in \left\{2,3,4\right\}$ este nevoie de cel puțin 2 ritualuri.
Pentru $n=4$ $r=2$ valorile lui E pentru care nu se poate deschide camera sunt 3,4, iar pentru $r=7$ toate valorile posibile a lui E permit deschiderea camerei.