AlgoLiga 2018

Stan Kowalsky, który od 2212 roku pracuje jako taksówkarz na Manhattanie, ma podobny problem jak jego (pra)⁶dziadek John. Zastanawia się ile punktów docelowych znajduje się w zasięgu jego międzywymiarowej taksówki?

Stan "przewozi" swoich pasażerów pomiędzy punktami kratowymi w przestrzeni k-wymiarowej, wykonując międzywymiarowe skoki teleportacyjne swoją nowoczesną taksówką. Może dostać się w dowolne miejsce, ale sposób poruszania się jest analogiczny do tego, jaki musiał stosować jego przodek, wożąc pasażerów ulicami Manhattanu: W jednym skoku może zmienić położenie taksówki tylko w jednym wymiarze. Zakładając na przykład, że porusza się w przestrzeni pięciowymiarowej, to aby przenieść się z punktu o współrzędnych (3, 1, 8, 1, 2) do punktu (3, 7, 8, 1, 0), musi wykonać dwa skoki teleportacyjne. Pierwszy skok musi nastąpić do punktu (3, 7, 8, 1, 2) albo do punktu (3, 1, 8, 1, 0). Niezależnie od tego, ktorą trasę wybierze, jej długość wyniesie 8 jednostek. Ponieważ Stan zawsze wybiera najkrótszą trasę, to jej długość możemy uznać jako odległość pomiędzy punktem początkowym i końcowym.

Stan ma w baku taksówki taką ilość paliwa, która wystarczy na pokonanie trasy o pewnej określonej długości. Ile punktów docelowych znajduje się w zasięgu taksówki Stana?

Wejście

W pierwszej linii liczba przypadków testowych t (1 ≤ t ≤ 100000).
W każdej z kolejnych t linii dane dla jednego testu w następującej postaci: 
Najpierw liczba wymiarów przestrzeni, w ktorej porusza się Stan k (1 ≤ k ≤ 15000) a następnie liczba całkowita d, oznaczająca maksymalną odległość, na jaką może pojechać (0 ≤ d ≤ 15000).

Wyjście

Dla każdego przypadku testowego, w osobnej linii, jedna liczba całkowita określająca liczbę skrzyżowań jakie znajdują się w zasięgu taksówki Stana modulo 18446744073709551616.

Przykład

Wejście:
3
3 0
2 1
4 2

Wyjście:
1
5
41