Planeta Bin-Bin

Treść

W odległej galaktyce Duo-Duo, na planecie Bin-Bin żyje sobie rasa Bin-Binitów. Budowa ciała Bin-Binitów bardzo przypomina ludzką. Odróżnia nas od siebie kolor skóry (Bin-Binici są zieleni) oraz liczba palców na każdej z kończyn. Mieszkańcy planety Bin-Bin posiadają po dwa palce na każdej z rąk i nóg. Mniejsza liczba palców niesie za sobą wiele korzyści. Obcinanie paznokci trwa zdecydowanie krócej, produkcja rękawiczek jest znacznie prostsza, a wydatki na pierścionki są o wiele niższe niż na Ziemi. Oprócz tego Bin-Binici posługują się prostszym, dwójkowym systemem liczbowym.

Do obliczania wartości wyrażeń typu (a + b)ⁿ stosuje się tu tzw. wzór Bintona na dwumian:

Obliczanie współczynników c_n,k, podobnie jak na Ziemi nie jest zadaniem trywialnym, zwłaszcza gdy n jest dużą, 20- lub 30-cyfrową liczbą. Bin-Biniccy informatycy postanowili rozwiązać ten problem przez napisanie oprogramowania, które będzie obliczać współczynniki c_n,k. Aby uprościć zadanie zdecydowali się obliczać każdą cyfrę wyniku oddzielnie, a następnie składać otrzymane wyniki w końcowy rezultat. Tobie, jako zaprzyjaźnionemu programiście z Ziemi, przypadła w udziale procedura obliczająca najmniej znaczącą cyfrę wyniku. Napisz program, który będzie taką procedurę zawierał.

Wejście

Dane podawane są na standardowe wejście. W pierwszym wierszu podana jest liczba N (1<=N<=20) zestawów danych. Dalej podawane są zestawy danych zgodnie z poniższym opisem:

Jeden zestaw danych

Jeden zestaw danych obejmuje dwa wiersze. W pierwszym podana jest liczba n, a w drugim k (0<=k<=n). Obie liczby podane są w postaci dwójkowej, a ich długość nie przekracza 30 cyfr.

Wyjście

Wyniki programu powinny być wypisywane na standardowe wyjście. W kolejnych wierszach należy podać odpowiedzi obliczone dla kolejnych zestawów danych. Wynikiem dla jednego zestawu jest najmniej znacząca cyfra współczynnika c_n,k dwumianu Bintona.

Przykład

dane wejściowe:
2
101
1
100000000000000000000000000000
1001010010000110101111

wynik:
1
0