cabana

Cabana

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

Poveste şi cerinţă...

În pădurea cu alune, aveau o cabană $N$ pitici. În cabană sunt exact $K$ camere în care se poate dormi. Cum somnul nu este deloc de neglijat în lumea piticilor, aceştia se joacă înainte de culcare astfel: Piticii intră pe rând în cabană şi se duc în camera în care vor dormi. Un pitic îşi alege camera în care va dormi în felul următor:
 
* Se duce în camera care a fost aleasă de cât mai puţini pitici.
* Dacă sunt mai multe camere cu această proprietate, piticul va alege oricare dintre acestea.
 
Când ajunge Albă ca Zăpada în cabană, aceasta se întreabă:
 
* Oare în câte moduri poate fi ocupată cabana de cei $N$ pitici?
 
Două moduri de ocupare a cabanei se consideră distincte dacă există cel puţin un pitic care să se afle într-o cameră distinctă.

h2. Date de intrare

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

Fişierul de intrare $cabana.in$ conţine pe prima linie un număr natural $T$, reprezentând numărul de teste. Pe urmatoarele $T$ linii, se vor găsi două numere $N$ şi $K$, având semnificaţia din enunţ.

h2. Date de ieşire

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

În fişierul de ieşire $cabana.out$ se vor găsi $T$ linii, pe fiecare linie $i$ găsindu-se răspunsul la întrebarea $i$.

h2. Restricţii

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

* $1 ≤ T ≤ 1.000$
* $1 ≤ N ≤ 10^18^$
* $1 ≤ K ≤ 1.000.000$

h2. Exemplu