Cho một xâu DNA ~S~ gồm các ký tự {A, C, G, T}. Bạn sẽ làm việc trên một xâu ~T~, ban đầu có giá trị rỗng. Tìm số thao tác sao chép nhỏ nhất để biến ~T~ thành một xâu cho trước. Biết rằng mỗi thao tác sao chép có một trong hai dạng:

• sao chép ~S~ ~i~ ~j~ ~k~: sao chép đoạn ~S[i~ ...~j]~ vào xâu ~T~ bắt đầu từ vị trí ~k~
• sao chép ~T~ ~i~ ~j~ ~k~: sao chép đoạn ~T[i~ ...~j]~ vào xâu ~T~ bắt đầu từ vị trí ~k~

Lưu ý nếu ~i > j~ có nghĩa là ta sao chép đoạn xâu theo thứ tự ngược. Mỗi ký tự trong ~T~ chỉ được tạo ra đúng một lần, nghĩa là không được sao chép đè lên ký tự đó.

Ví dụ: Với ~S =~ "ACTG" hãy tạo ~T =~ "GTACTATTATA"

1. Tạo GT ....... bằng cách sao chép và đảo xâu "TG" từ ~S~.
2. Tạo GTAC ......bằng cách sao chép "AC" từ ~S~.
3. Tạo GTAC ...TA ...bằng cách sao chép "TA" từ ~T~.
4. Tạo GTAC ...TAAT bằng cách sao chép và đảo xâu "TA" từ ~T~.
5. Tạo GTACAATTAAT bằng cách sao chép "AAT" từ ~T~.

Input

Dòng đầu tiên chứa ~t~ là số bộ test. Với mỗi test có hai dòng chứa xâu ~S~ và xâu ~T~ với độ dài không quá ~18~.

Output

Với mỗi test, in ra số thao tác sao chép ít nhất để tạo ra ~T~ từ ~S~, hoặc in ra "impossible" nếu không thể làm được.

Sample Input

5
ACGT
GTAC
A
C
ACGT
TGCA
ACGT
TCGATCGA
A
AAAAAAAAAAAAAAAAAA

Sample Output

2
impossible
1
4
6