Bakterie

Treść

Profesor Ciekawski porzucił ostatnimi czasy nauki ścisłe i zajął się mikrobiologią. W swoim tajnym laboratorium w podziemiach Politechniki Białostockiej zajmuje się hodowlą bakterii. Dzięki starannie prowadzonej selekcji genetycznej oraz szczególnym właściwościom wody w kranach Politechniki, udało mu się uzyskać nowy gatunek, Policteria. Bakterie te nie rozmnażają się jak wiele innych organizmów jednokomórkowych. Liczba bakterii w kolonii jest stała i zależy od podgatunku. Podgatunki te profesor oznaczył symbolami K-1, K-2, K-3, itd. Co więcej całkowita masa kolonii jest stała, a pojedyncza bakteria może ważyć dokładnie 1,2,3,… lub 9 jednostek. Dzięki tym właściwościom każdą kolonię można przedstawić jako K-cyfrową liczbę, zwaną liczbą P. Po licznych eksperymentach profesor odkrył, że liczby P dla kolejno następujących po sobie pokoleń bakterii stanowią ciąg rosnący o możliwie najmniej zmieniających się wartościach. Pierwsze pokolenie jest zawsze uzyskiwane sztucznie, natomiast po osiągnięciu maksymalnej możliwej liczby P, kolonia przestaje ewoluować. Przykładowo, jeżeli liczba P pierwszego pokolenia podgatunku K-3 wynosi 213, kolejne pokolenia będą reprezentowane przez liczby 222, 231, 312, 321 i 411.

W celu zbadania dynamiki przeistaczania się kolonii, profesor Ciekawski w określonych odstępach czasu zmierzył masy poszczególnych bakterii, otrzymując w ten sposób liczby P. Teraz na podstawie zebranych danych chciałby wiedzieć, które z kolei pokolenia reprezentują wyniki pomiarów. To zadanie powierzył Tobie, swemu najbardziej zaufanemu asystentowi. Napisz program, który na podstawie liczb P dla pierwszego i nieznanego, badanego pokolenia obliczy, które to z kolei pokolenie.

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

Pierwszy wiersz zestawu danych zawiera liczbę całkowitą k (2<=k<=100) oznaczającą podgatunek bakterii. Drugi wiersz zawiera k-cyfrową liczbę P pierwszego pokolenia bakterii. Trzeci wiersz zawiera k-cyfrową liczbę P definiującą badane pokolenie.

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 numer badanego pokolenia bakterii. Dane wejściowe są tak dobrane, że numer ten nie przekracza 10¹⁵.

Przykład

dane wejściowe:
2
2
38
74
3
213
411

wynik:
5
6