给定由字符{A,C,G,T}组成的DNA字符串S，计算出最小需要几步，就能通过复制操作构造出另一DNA字符串T. 你可以从复制S，也可以复制你已经构成的T，复制的字符串可以倒转，你可以在任何拼接这些字符串。复制字符串时，只能复制连续的连续的部分，你不能复制尚未拼接的部分。所有复制出来的字符串都必须作为最终T的一部分。比如：S = “ACTG” ，来构造T = “GTACTATTATA”

1. 
   复制并倒转S的子串"TG"，得到GT......... 。


2. 
   复制S的子串"AC" ，得到GTAC.......  。


3. 
   复制T的已有子串"TA"，得到GTAC...TA..。


4. 
   复制并倒转T的已有子串"TA"，得到GTAC...TAAT。


5. 
    复制T的已有子串"AAT"，得到GTACAATTAAT。

第一行有一个正整数 t ，表示数据组数(不多于100)。每一组数据有两行，第一行是字符串S ，其长度m符合1 ≤ m ≤ 18, 第二行是字符串T，其长度n,符合1 ≤ n ≤ 18.

每组数据输出一行，如果不能构造，则输出"impossible"，否则输出最少需要的复制操作次数。

5
ACGT
GTAC
A
C
ACGT
TGCA
ACGT
TCGATCGA
A
AAAAAAAAAAAAAAAAAA

2
impossible
1
4
6