AlgoLiga 2018

Bajtek rozpoczął właśnie pracę w Biurze Podróży "Bajtour". Szefowa zleciła mu pierwsze zadanie - ma zaplanować różne warianty wycieczki do najsłynniejszej bajtockiej doliny, na obszarze której znajduje się wiele historycznych zamków.

Każda wycieczka musi rozpoczynać się w położonej na południowym końcu doliny wiosce Bitowice Dolne, a kończyć się na północnym skraju doliny w znanej uzdrowiskowej miejscowości Bajtusko-Zdrój. Podczas wycieczki nie wszystkie zamki muszą być zwiedzane. Każdy wariant musi się różnić od pozostałych właśnie tym, które warownie obejrzą uczestnicy wycieczki. Szefowa postawiła jednak dwa warunki. Po pierwsze, wybrane zamki trzeba zwiedzać w takiej kolejności, w jakiej usytuowane są w dolinie. Po drugie, liczba kolejnych warowni pomijanych na trasie, pomiędzy miejscami, w których zatrzymuje się wycieczka, nie może być większa od pewnej założonej wartości.  Bajtek uznał, że potrzebny mu jest przede wszystkim program, który obliczy, ile wariantów wycieczki zgodnych z warunkami można zaplanować.

Wejście

W pierwszej linii liczba testów t (1 ≤ t ≤ 10). 

W każdej z kolejnych t linii dwie liczby całkowite. Liczba wszystkich zamków n (1 ≤ n ≤ 10⁷), oraz maksymalna liczba kolejnych niezwiedzanych zamków k (0 ≤ k ≤ 100, k ≤ n). 

Wyjście

Dla każdego testu, w osobnej linii, jedna liczba całkowita oznaczająca liczbę możliwych wariantów wycieczki podana modulo 18446744073709551616.

Przykład

Wejście:
2
2 2 
3 1

Wyjście:
4
5 

Uwaga

W zadaniu obowiązuje zmniejszony do 4MB limit pamięci.