Drabina

Limit pamięci: 32 MB

Bajtek wchodzi na drabinę. Może on jednym krokiem wejść jeden szczebelek wyżej lub dwa szczebelki wyżej. Zastanawiamy się, na ile różnych sposobów może on wejść na szczyt (ostatni szczebelek) drabiny.

Liczba tych sposobów może być bardzo duża, więc interesuje nas tylko reszta z dzielenia przez liczbę .

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę zestawów danych. Kolejnych wierszy zawiera po dwie liczby całkowite (), oznaczające odpowiednio liczbę szczebelków drabiny i wartość z treści zadania.

Wyjście

Dla każdego zestawu danych powinna się znaleźć w nowej linii jedna liczba całkowita, równa liczbie sposobów dojścia na szczyt drabiny modulo (reszta z dzielenia) .

Przykład

Dla danych wejściowych:

5
3 2
3 1
4 2
1 1
2 1

poprawną odpowiedzią jest:

3
1
1
1
0

Autor zadania: Jacek Tomasiewicz.