Pku3633 Copying DNA

给定两个由字符集 $\{A,C,G,T\}$ 构成的 DNA 字符串 $S$ 和 $T$，要求用尽量少的步数从 $S$ 构造出 $T$。

每一步可以从 $S$ 的某个连续子串，或当前已经构造出的 $T$ 的某个片段中拷贝一个连续子串，并选择是否将拷贝得到的字符串反转。得到的片段可以随时与其他片段合并，但不能拆分，且所有得到的片段都必须用于构造最终的 $T$。从当前构造出的 $T$ 中拷贝字符串时，只能从同一个片段中拷贝。

例如，从 $S=\text{ACTG}$ 构造 $T=\text{GTACTATTATA}$：

1. 从 $S$ 中拷贝并反转 $\text{TG}$，得到 $\text{GT}$；
2. 从 $S$ 中拷贝 $\text{AC}$，得到 $\text{GTAC}$；
3. 从当前片段中拷贝 $\text{TA}$；
4. 从当前片段中拷贝并反转 $\text{TA}$；
5. 从当前片段中拷贝 $\text{AAT}$。

求构造 $T$ 所需的最少拷贝操作次数。

输入格式

第一行包含一个整数 $t$，表示测试数据组数，满足 $1\le t\le 100$。

接下来每组测试数据包含两行：

• 第一行包含字符串 $S$，其长度为 $m$，满足 $1\le m\le 18$；
• 第二行包含字符串 $T$，其长度为 $n$，满足 $1\le n\le 18$。

输出格式

对于每组测试数据，输出一行：

• 如果可以从 $S$ 构造出 $T$，输出所需的最少拷贝操作次数；
• 如果无法构造出 $T$，输出 impossible。

样例输入

5
ACGT
GTAC
A
C
ACGT
TGCA
ACGT
TCGATCGA
A
AAAAAAAAAAAAAAAAAA

样例输出

2
impossible
1
4
6

数据范围

• 测试数据组数满足 $1\le t\le 100$；
• 字符串 $S$ 的长度为 $m$，满足 $1\le m\le 18$；
• 字符串 $T$ 的长度为 $n$，满足 $1\le n\le 18$；
• $S$ 和 $T$ 均只包含字符 $A$、$C$、$G$、$T$。

来源与许可

本题题面与测试数据整理自 BZOJ 2485。

样例 1

输入

5
ACGT
GTAC
A
C
ACGT
TGCA
ACGT
TCGATCGA
A
AAAAAAAAAAAAAAAAAA

输出

2
impossible
1
4
6