SP3078 COPYDNA - Copying DNA

进化是一个看似随机的过程，其工作方式与我们用来解决复杂组合问题的某些近似方法相似。然而，你现在需要解决的是一种完全不同的任务。 你需要根据给定的由字母 {A, C, G, T} 组成的 DNA 字符串 $S$，寻找生成另一个字符串 $T$ 所需的最少复制操作次数。在这个过程中，你可以对复制的字符串进行反转，并且可以从字符串 $S$ 和部分构建中的 $T$ 中复制。复制得到的片段可以在任意时间拼接在一起。需要注意的是，你只能复制部分生成的 $T$ 中的连续部分，并且所有被复制的字符串最终都必须得到使用。 例如：从 $S = \text{“ACTG”}$ 生成 $T = \text{“GTACTATTATA”}$ 的过程如下： 1. 从 $S$ 复制并反转 "TG" 得到 GT.........。 2. 从 $S$ 复制 "AC" 接上，得到 GTAC.......。 3. 从部分生成的 $T$ 中复制 "TA" 得到 GTAC...TA..。 4. 从部分生成的 $T$ 中复制并反转 "TA" 得到 GTAC...TAAT。 5. 从部分生成的 $T$ 中复制 "AAT" 得到最终的 GTACAATTAAT。

第一行输入一个整数 $t$（$1 \le t \le 100$），代表测试用例的数量。每个测试用例包含两行，第一行是字符串 $S$（长度为 $m$，$1 \le m \le 18$），第二行是字符串 $T$（长度为 $n$，$1 \le n \le 18$）。

对每个测试用例，输出生成 $T$ 所需的最少复制操作次数。如果无论如何也无法完成生成，则输出“impossible”。 **本翻译由 AI 自动生成**