시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 22 5 5 26.316%

문제

상근이는 졸업 프로젝트로 DNA 복사를 시뮬레이션 하기로 했다.

DNA 문자열 S는 알파벳 {A, C, G, T}로만 이루어져 있다. 이때, 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가 주어진다. (1 ≤ t ≤ 100) 다음 줄에는 문자열 S가, 그 다음 줄에는 T가 주어진다. 주어지는 문자열의 길이는 모두 1보다 크거나 같고, 18보다 작거나 같다.

출력

각 테스트 케이스에 대해서 T를 만드는데 필요한 복사 횟수를 출력한다. 만약, 불가능한 경우에는 "impossible"을 출력한다.

예제 입력 1

5
ACGT
GTAC
A
C
ACGT
TGCA
ACGT
TCGATCGA
A
AAAAAAAAAAAAAAAAAA

예제 출력 1

2
impossible
1
4
6
W3sicHJvYmxlbV9pZCI6IjUwNTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJETkEgXHViY2Y1XHVjMGFjIiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2NvcHlkbmEucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjIyOXB4OyB3aWR0aDoxMzdweFwiIFwvPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM4NzhcdWM1YzUgXHVkNTA0XHViODVjXHVjODFkXHVkMmI4XHViODVjIEROQSBcdWJjZjVcdWMwYWNcdWI5N2MgXHVjMmRjXHViYmFjXHViODA4XHVjNzc0XHVjMTU4IFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkROQSBcdWJiMzhcdWM3OTBcdWM1ZjQgU1x1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjMge0EsIEMsIEcsIFR9XHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0YywgRE5BIFx1YmIzOFx1Yzc5MFx1YzVmNCBUXHViOTdjIFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YmNmNVx1YzBhY1x1Yzc1OCBcdWNkNWNcdWMxOGMgXHVkNjlmXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YmNmNVx1YzBhY1x1YjI5NCBTXHVjNjQwIFRcdWM3NTggXHVjNzdjXHViZDgwXHVjNWQwXHVjMTFjIFx1YmNmNVx1YzBhY1x1Yjk3YyBcdWQ1NzRcdWM1N2MgXHVkNTU4XHViYTcwLCBcdWI0YTRcdWM5ZDFcdWM1YjRcdWMxMWMgXHViY2Y1XHVjMGFjXHViOTdjIFx1ZDU3NFx1YjNjNCBcdWI0MWNcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVkNTZkXHVjMGMxIFx1YzVmMFx1YzE4ZFx1YjQxYyBcdWJkODBcdWJkODRcdWI5Y2MgXHViY2Y1XHVjMGFjXHViOTdjIFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWJjZjVcdWMwYWNcdWQ1NWMgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWNkNWNcdWM4ODUgVFx1YzVkMCBcdWQzZWNcdWQ1NjhcdWI0MThcdWM1YjQgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgUyA9ICZxdW90O0FDVEcmcXVvdDssIFQgPSAmcXVvdDtHVEFDVEFUVEFUQSZxdW90O1x1Yzc3OCBcdWFjYmRcdWM2YjBcdWI5N2MgXHVjMGI0XHVkM2I0XHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPlx1YmEzY1x1YzgwMCBTXHVjNWQwXHVjMTFjICZxdW90O1RHJnF1b3Q7XHViOTdjIFx1YmNmNVx1YzBhY1x1ZDU1YyBcdWIyZTRcdWM3NGMgXHViNGE0XHVjOWQxXHVjNWI0XHVjMTFjIFx1YmQ5OVx1YzVlY1x1YzExYyA8Y29kZT5HVC4uLi4uLi4uLjxcL2NvZGU+XHViOTdjIFx1YjljY1x1YjRlMFx1YjJlNC48XC9saT5cclxuXHQ8bGk+U1x1YzVkMFx1YzExYyBBQ1x1Yjk3YyBcdWJjZjVcdWMwYWNcdWQ1NzQgPGNvZGU+R1RBQy4uLi4uLi48XC9jb2RlPlx1Yjk3YyBcdWI5Y2NcdWI0ZTBcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlRcdWM3NTggXHVjNzdjXHViZDgwXHVjNzc4IFRBXHViOTdjIFx1YmNmNVx1YzBhY1x1ZDU3NFx1YzExYyA8Y29kZT5HVEFDLi4uVEEuLjxcL2NvZGU+XHViOTdjIFx1YjljY1x1YjRlMFx1YjJlNC48XC9saT5cclxuXHQ8bGk+VFx1YzVkMFx1YzExYyBUQVx1Yjk3YyBcdWJjZjVcdWMwYWNcdWQ1NWMgXHViMmU0XHVjNzRjIFx1YjRhNFx1YzlkMVx1YzViNFx1YzExYyBcdWJkOTlcdWM1ZWNcdWMxMWMgPGNvZGU+R1RBQy4uLlRBQVQ8XC9jb2RlPlx1Yjk3YyBcdWI5Y2NcdWI0ZTBcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YywgVFx1Yzc1OCBcdWM3N2NcdWJkODBcdWM3NzggQUFUXHViOTdjIFx1YmNmNVx1YzBhY1x1ZDU3NCA8Y29kZT5HVEFDQUFUVEFBVDxcL2NvZGU+XHViOTdjIFx1YjljY1x1YjRlMFx1YjJlNC48XC9saT5cclxuPFwvb2w+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCB0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyB0ICZsZTsgMTAwKSBcdWIyZTRcdWM3NGMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNCBTXHVhYzAwLCBcdWFkZjggXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHViYWE4XHViNDUwIDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMThcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgVFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YmNmNVx1YzBhYyBcdWQ2OWZcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YmQ4OFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgJnF1b3Q7aW1wb3NzaWJsZSZxdW90O1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTA1NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNvcHlpbmcgRE5BIiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2NvcHlkbmEucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjIyOXB4OyB3aWR0aDoxMzdweFwiIFwvPkV2b2x1dGlvbiBpcyBhIHNlZW1pbmdseSByYW5kb20gcHJvY2VzcyB3aGljaCB3b3JrcyBpbiBhIHdheSB3aGljaCByZXNlbWJsZXMgY2VydGFpbiBhcHByb2FjaGVzIHdlIHVzZSB0byBnZXQgYXBwcm94aW1hdGUgc29sdXRpb25zIHRvIGhhcmQgY29tYmluYXRvcmlhbCBwcm9ibGVtcy4gWW91IGFyZSBub3cgdG8gZG8gc29tZXRoaW5nIGNvbXBsZXRlbHkgZGlcdWZiMDBlcmVudC48XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBETkEgc3RyaW5nIFMgZnJvbSB0aGUgYWxwaGFiZXQge0EsQyxHLFR9LCBcdWZiMDFuZCB0aGUgbWluaW1hbCBudW1iZXIgb2YgY29weSBvcGVyYXRpb25zIG5lZWRlZCB0byBjcmVhdGUgYW5vdGhlciBzdHJpbmcgVC4gWW91IG1heSByZXZlcnNlIHRoZSBzdHJpbmdzIHlvdSBjb3B5LCBhbmQgY29weSBib3RoIGZyb20gUyBhbmQgdGhlIHBpZWNlcyBvZiB5b3VyIHBhcnRpYWwgVC4gWW91IG1heSBwdXQgdGhlc2UgcGllY2VzIHRvZ2V0aGVyIGF0IGFueSB0aW1lLiBZb3UgbWF5IG9ubHkgY29weSBjb250aWd1b3VzIHBhcnRzIG9mIHlvdXIgcGFydGlhbCBULCBhbmQgYWxsIGNvcGllZCBzdHJpbmdzIG11c3QgYmUgdXNlZCBpbiB5b3VyIFx1ZmIwMW5hbCBULiBFeGFtcGxlOiBGcm9tIFMgPSAmbGRxdW87QUNURyZyZHF1bzsgY3JlYXRlIFQgPSAmbGRxdW87R1RBQ1RBVFRBVEEmcmRxdW87PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+R2V0IDxjb2RlPkdULi4uLi4uLi4uPFwvY29kZT4gYnkgY29weWluZyBhbmQgcmV2ZXJzaW5nICZsZHF1bztURyZyZHF1bzsgZnJvbSBTLjxcL2xpPlxyXG5cdDxsaT5HZXQgPGNvZGU+R1RBQy4uLi4uLi48XC9jb2RlPiBieSBjb3B5aW5nICZsZHF1bztBQyZyZHF1bzsgZnJvbSBTLjxcL2xpPlxyXG5cdDxsaT5HZXQgPGNvZGU+R1RBQy4uLlRBLi48XC9jb2RlPiBieSBjb3B5aW5nICZsZHF1bztUQSZyZHF1bzsgZnJvbSB0aGUgcGFydGlhbCBULjxcL2xpPlxyXG5cdDxsaT5HZXQgPGNvZGU+R1RBQy4uLlRBQVQ8XC9jb2RlPiBieSBjb3B5aW5nIGFuZCByZXZlcnNpbmcgJmxkcXVvO1RBJnJkcXVvOyBmcm9tIHRoZSBwYXJ0aWFsIFQuPFwvbGk+XHJcblx0PGxpPkdldCA8Y29kZT5HVEFDQUFUVEFBVDxcL2NvZGU+IGJ5IGNvcHlpbmcgJmxkcXVvO0FBVCZyZHF1bzsgZnJvbSB0aGUgcGFydGlhbCBULjxcL2xpPlxyXG48XC9vbD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgaW5wdXQgZ2l2ZXMgYSBzaW5nbGUgaW50ZWdlciwgMSAmbGU7IHQgJmxlOyAxMDAsIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy4gVGhlbiBmb2xsb3csIGZvciBlYWNoIHRlc3QgY2FzZSwgYSBsaW5lIHdpdGggdGhlIHN0cmluZyBTIG9mIGxlbmd0aCAxICZsZTsgbSAmbGU7IDE4LCBhbmQgYSBsaW5lIHdpdGggdGhlIHN0cmluZyBUIG9mIGxlbmd0aCAxICZsZTsgbiAmbGU7IDE4LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBmb3IgZWFjaCB0ZXN0IGNhc2UgdGhlIG51bWJlciBvZiBjb3B5IG9wZXJhdGlvbnMgbmVlZGVkIHRvIGNyZWF0ZSBUIGZyb20gUywgb3IgJmxkcXVvO2ltcG9zc2libGUmcmRxdW87IGlmIGl0IGNhbm5vdCBiZSBkb25lLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==