Copying DNA

Copying DNA | JXNUOJ

translate ：

describe ：

Evolution is a seemingly random process , It works in a way similar to some of the methods we use to obtain approximate solutions to hard combinatorial problems . Now you have to do something completely different .
Given the alphabet {A,C,G,T} Medium DNA character string S, Find and create another string T Minimum number of replication operations required . You can reverse the string you copied , And from S And your clip copy part T. You can always put these parts together . You can only copy part of T A continuous part of , And it must be in the end T Use all copied strings in . in ​​ example ：
from S = “ACTG” establish T = “GTACTATTATA”
1. By getting from S Copy and reverse in “TG” To get GT.......
2. By getting from S Copy the “AC” To get GTAC.......
3. By from part T Copy the “TA” To get GTAC...TA...
4. By from part T Copy and reverse in “TA” To get GTAC...TAAT.
5. By from part T Copy the “AAT” To get GTACAATTAAT.
Input ：
The first line of input gives an integer ,1 <= t <= 100, Represents the number of test cases . then , For each test case , A row contains a length of 1 <= m <= 18 String S, And contains a length of 1 <= n <= 18 String T A line .
Output ：
Output from for each test case S establish T Number of replication operations required , If it can't be done , The output “ impossible ”.