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.</p>

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

입력 형식

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

출력 형식

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) 2^p.

예제 입력

5
3 2
3 1
4 2
1 1
2 1

예제 출력

3
1
1
1
0