Napisy wewnętrzne

Dane są dwa napisy. Należy obliczyć na ile sposobów można uzyskać napis drugi z napisu pierwszego poprzez wykreślenie niektórych liter.

Dane wejściowe:

W pierwszym wierszu wejścia znajduje się pojedyncza liczba C określająca liczbę przypadków testowych. W kolejnych 2 * C wierszach znajdują się przypadki testowe.

Każdy przypadek testowy złożony jest z dwóch wierszy, z których pierwszy zawiera napis (długości 1...10007), z którego wykreślane będą znaki w celu uzyskania napisu (o długości 1...1012) zamieszonego w wierszu drugim. Wszystkie napisy składają się z małych i dużych liter alfabetu angielskiego oraz z cyfr dziesiętnych. Wynik zawsze jest mniejszy niż 10⁹.

Dane wyjściowe:

Dane wyjściowe zawierają C wierszy. W kolejnych wierszach znajdują się odpowiedzi dla kolejnych przypadków testowych.

Przykładowe dane wejściowe:

2
abba
aba
barabara
ara
        

Przykładowe dane wyjściowe:

2
6