Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_30_07 - Taksówka na Manhattanie 7

Stan Kowalsky, który od 2212 roku pracuje jako taksówkarz na Manhattanie, ma podobny problem jak jego (pra)6dziadek 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 (≤ 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 (1k15000) a następnie liczba całkowita d, oznaczająca maksymalną odległość, na jaką może pojechać (0d15000).

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

Dodane przez:Witold Długosz
Data dodania:2016-10-24
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie: ALGOLIGA 30
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.