Frumusete

frumusete

== include(page="template/taskheader" task_id="frumusete") ==

Cui nu îi plac numerele frumoase? Fie un număr $N$, în baza $10$. Definim astfel gradul de frumuseţe al lui $N$ ca fiind numărul de secvenţe de lungime $2$ pline de $1$ existente în scrierea sa în baza 2. De exemplu:
 
* $11 ~(10)~ = 1011 ~(2)~$, deci gradul de frumuseţe al lui $11$ este $1$.
* $27 ~(10)~ = 11011 ~(2)~$, deci gradul de frumuseţe al lui $27$ este $2$.
* $15 ~(10)~ = 1111 ~(2)~$, deci gradul de frumuseţe al lui $15$ este $3$.
 
Se dau $T$ - numărul de teste, iar pentru fiecare test trei numere naturale, $A$, $B$, $K$. Pentru fiecare test, să se răspundă la următoarea întrebare:
 
* Câte numere naturale $X$, $A ≤ X ≤ B$, au gradul de frumuseţe egal cu $K$?

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $frumusete.in$ conţine pe prima linie numărul natural $T$. Pe fiecare dintre următoarele $T$ linii se vor găsi trei numere naturale, $A$, $B$, $K$, având semnificaţia din enunţ.

Fişierul de intrare $frumusete.in$ ...

h2. Date de ieşire

În fişierul de ieşire $frumusete.out$ se vor găsi $T$ linii, pe linia $i$ găsindu-se răspunsul pentru testul $i$.

În fişierul de ieşire $frumusete.out$ ...

h2. Restricţii

* $1 ≤ T ≤ 10.000$
* $1 ≤ A ≤ B ≤ 10^18^$
* $1 ≤ K ≤ 60$

* $... ≤ ... ≤ ...$

h2. Exemplu