DNA Copy

Sang-geun decided to simulate DNA copying for his graduation project.

A DNA string consists only of the letters A, C, G, and T. Given a source string $S$, find the minimum number of copy operations needed to build a target string $T$.

Each copy operation follows these rules:

• The copied piece must be a contiguous part of $S$, or a contiguous part of $T$ that has already been built.
• The piece may be reversed before it is placed.
• Each copied piece fills one contiguous segment of $T$; once every segment is filled, $T$ is complete.

In other words, every position of the finished $T$ is filled by exactly one copy, taken either from $S$ or from an already-built part (reversal allowed). The order of filling is free, but a part used as a source must already be complete at the moment it is copied.

For example, with $S =$ ACTG and $T =$ GTACAATTAAT, $T$ can be built in $5$ copies:

1. Copy TG from $S$ and reverse it to GT → GT.........
2. Copy AC from $S$ → GTAC.......
3. Copy TA, a part already built → GTAC...TA..
4. Copy TA and reverse it to AT → GTAC...TAAT
5. Copy AAT, a part already built → GTACAATTAAT

The first line contains the number of test cases $t$ ($1 \le t \le 100$). Each test case consists of two lines: the first line contains the string $S$ and the second line contains the string $T$. Both strings consist only of the letters A, C, G, and T, and their lengths are between $1$ and $18$, inclusive.

For each test case, print on its own line the minimum number of copies needed to build $T$. If it is impossible, print impossible.