== include(page="template/taskheader" task_id="frumusete") ==
Poveste şi cerinţă...
Cui nu îi plac numerele frumoase? Fie un număr $N$, în baza $10$. Definim 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 două numere naturale, $K$ şi $N$. Pentru fiecare test, să se răspundă la următoarea întrebare:
* Câte numere naturale $X$, $0 ≤ X ≤ N$, au gradul de frumuseţe egal cu $K$?
Răspunsul se cere modulo $666013$.
h2. Date de intrare
Fişierul de intrare $frumusete.in$ ...
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 două numere naturale, $K$ şi $N$, având semnificaţia din enunţ. Pentru că suntem în perioada sărbătorilor, numărul $N$ vă este dat în baza $2$.
h2. Date de ieşire
În fişierul de ieşire $frumusete.out$ ...
Î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$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $T = 20.000$
* $0 ≤ K ≤ 1000$
* $0 ≤ N < 2^1000^$
* $Vă recomandăm să folosiţi *gets* pentru a citi numerele din fişierul de intrare şi nu cin.$
h2. Exemplu
table(example). |_. frumusete.in |_. frumusete.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3
3 11111
4 1010101
0 10
| 2
2
3
|
h3. Explicaţie
...
Sunt două numere mai mici sau egale decât $31 = 11111$ cu gradul de frumuseţe $3$: $15 = 1111$ şi $30 = 11110$.
Sunt două numere mai mici sau egale decât $85 = 1010101$ cu gradul de frumuseţe $4$: $31 = 11111$ şi $62 = 111110$.
Sunt trei numere mai mici sau egale decât $2 = 10$ cu gradul de frumuseţe $0$: $0 = 0$, $1 = 1$, $2 = 10$.
== include(page="template/taskfooter" task_id="frumusete") ==
