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

Astăzi se împlineşte exact $1$ lună de la începutul relaţiei celor doi amorezi, Antonio şi Antonia. Tocmai pentru că Antonio a uitat să îi cumpere lalele Antoniei, acestea fiind florile ei preferate, ea s-a gândit să îl pedepsească. Prin urmare, Antonia îi va pune lui Antonio $Q$ întrebări:

Astăzi se împlineşte exact $1$ lună de la începutul relaţiei celor doi amorezi, Antonio şi Antonia. Tocmai pentru că Antonio a uitat să îi cumpere lalele Antoniei, acestea fiind florile ei preferate, ea s-a gândit să îl pedepsească. Prin urmare, Antonia îi va pune lui Antonio următoarea întrebare:

* Antonio dragă, îţi voi da un număr natural $N$. Vreau să îmi spui în câte moduri se poate obţine acest număr doar prin $K$ operaţii de înmulţire cu numere pare. Ca să ai şi timp să îmi cumperi lalele, îţi cer acest număr modulo $666013$.

h2. Date de intrare

Fişierul de intrare $oluna.in$ conţine pe prima linie numărul Q, reprezentând numărul de întrebări puse de Antonia. Pe următoarele $Q$ linii se vor găsi câte două numere naturale, $N$ şi $K$, separate între ele printr-un spaţiu, având semnificaţia din enunţ.

Fişierul de intrare $oluna.in$ conţine pe prima linie două numere naturale $N$ şi $K$, separate între ele printr-un spaţiu, având semnificaţia din enunţ.

h2. Date de ieşire

În fişierul de ieşire $oluna.out$ se vor gasi $Q$ linii: fiecare linie $i$ conţine un singur număr natural, reprezentând răspunsul la întrebarea numărul $i$.

În fişierul de ieşire $oluna.out$ se va găsi un singur număr natural, reprezentând răspunsul la întrebarea Antoniei.

h2. Restricţii

h2. Exemplu
table(example). |_. oluna.in |_. oluna.out |_. Explicaţie |

| 2
6 1
5 1
| 1
0
| Numărul 6 se poate obţine într-un singur mod, printr-o înmulţire cu 6. Numărul 5 nu poate fi obţinut conform cerinţei.

| 10 1
| 0
| Numărul 10 nu poate fi obţinut conform cerinţei.

|

| 1
60 2

| 60 2

| 4
| Cele 4 posibilităţi sunt: 1 * 2 * 30, 1 * 30 * 2, 1 * 6 * 10, 1 * 10 * 6.
|