== 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$. Trebuie să ştii ca numărul acesta a fost iniţial egal cu $1$. Vreau să îmi spui în câte moduri am putut obţine numărul $N$ prin *exact* $K$ operaţii de înmulţire, toate dintre acestea 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 un număr natural $Q$, reprezentând numărul de întrebări ale Antoniei. Pe fiecare din următoarele $Q$ linii, se vor găsi 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 găsi $Q$ linii. Pe fiecare linie $i$, se va găsi un singur număr natural, reprezentând răspunsul la întrebarea $i$ a Antoniei.

Î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

* $1 ≤ Q ≤ 100$

* $1 ≤ N ≤ 10^12^$
* $1 &le; K < 50$
h2. Exemplu
table(example). |_. oluna.in |_. oluna.out |_. Explicaţie |

| 2
5 1
10 1

| 5 1

| 0

1
| Numărul 5 nu poate fi obţinut conform cerinţei. Numărul 10 poate fi obţinut doar printr-o înmulţire cu 10.

| Numărul 5 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.
|