Knuth, Morris i Pratt

To zadanie pochodzi z Kółka Informatycznego w Staszicu.

Ciekawe, że też niektórzy ludzie nie mają innych problemów... Otóz tym razem Knuth z kumplami postanowił wyszukać sobie stringa w stringu. Ale Morris z Prattem go wyśmiali i wymyślili coś trudniejszego - wyszukać stringa w stringu, tyle, że ten pierwszy może mieć gwiazdki reprezentujące dowolny ciąg literek (być może pusty). No i zakasali rękawy, myślą... i nic! Pomóż im!

Wejście

W pierwszym wierszu będzie ilość przykładów, w kolejnych wierszach dwa niepuste ciągi liter alfabetu łacińskiego oddzielone spacją. W pierwszym mogą być dodatkowo gwiazdki (max. 10). Oba będą oczywiście nie dłuższe niż milion.

Wyjście

Dla każdego z przykładów należy określić czy pierwszy jest gdzieś w drugim i wypisać 'Jest.' lub 'Nie ma go.'.

Przykład

Dla danych wejściowych:

6
Ala*Kota AlaMaKota
LA fasola
sol*a** fasolka
*** B
dwa razdwatrzy
dwa*raz razdwa

poprawną odpowiedzią jest:

Jest.
Nie ma go.
Jest.
Jest.
Jest.
Nie ma go.