시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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
W3sicHJvYmxlbV9pZCI6IjUwNTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJETkEgXHViY2Y1XHVjMGFjIiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2NvcHlkbmEucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjIyOXB4OyB3aWR0aDoxMzdweFwiIFwvPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM4NzhcdWM1YzUgXHVkNTA0XHViODVjXHVjODFkXHVkMmI4XHViODVjIEROQSBcdWJjZjVcdWMwYWNcdWI5N2MgXHVjMmRjXHViYmFjXHViODA4XHVjNzc0XHVjMTU4IFx1ZDU1OFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkROQSBcdWJiMzhcdWM3OTBcdWM1ZjQgU1x1YjI5NCBcdWM1NGNcdWQzMGNcdWJjYjMge0EsIEMsIEcsIFR9XHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIEROQSBcdWJiMzhcdWM3OTBcdWM1ZjQgVFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWJjZjVcdWMwYWNcdWM3NTggXHVjZDVjXHVjMThjIFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJjZjVcdWMwYWNcdWIyOTQgU1x1YzY0MCBUXHVjNzU4IFx1Yzc3Y1x1YmQ4MFx1YzVkMFx1YzExYyBcdWJjZjVcdWMwYWNcdWI5N2MgXHVkNTc0XHVjNTdjIFx1ZDU1OFx1YmE3MCwgXHViNGE0XHVjOWQxXHVjNWI0XHVjMTFjIFx1YmNmNVx1YzBhY1x1Yjk3YyBcdWQ1NzRcdWIzYzQgXHViNDFjXHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1ZDU2ZFx1YzBjMSBcdWM1ZjBcdWMxOGRcdWI0MWMgXHViZDgwXHViZDg0XHViOWNjIFx1YmNmNVx1YzBhY1x1Yjk3YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHViY2Y1XHVjMGFjXHVkNTVjIFx1YmIzOFx1Yzc5MFx1YzVmNFx1Yzc0MCBcdWQ1NmRcdWMwYzEgXHVjZDVjXHVjODg1IFRcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFMgPSAmcXVvdDtBQ1RHJnF1b3Q7LCBUID0gJnF1b3Q7R1RBQ1RBVFRBVEEmcXVvdDtcdWM3NzggXHVhY2JkXHVjNmIwXHViOTdjIFx1YzBiNFx1ZDNiNFx1YmNmNFx1Yzc5MC48XC9wPlxyXG5cclxuPG9sPlxyXG5cdDxsaT5cdWJhM2NcdWM4MDAgU1x1YzVkMFx1YzExYyAmcXVvdDtURyZxdW90O1x1Yjk3YyBcdWJjZjVcdWMwYWNcdWQ1NWMgXHViMmU0XHVjNzRjIFx1YjRhNFx1YzlkMVx1YzViNFx1YzExYyBcdWJkOTlcdWM1ZWNcdWMxMWMgPGNvZGU+R1QuLi4uLi4uLi48XC9jb2RlPlx1Yjk3YyBcdWI5Y2NcdWI0ZTBcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlNcdWM1ZDBcdWMxMWMgQUNcdWI5N2MgXHViY2Y1XHVjMGFjXHVkNTc0IDxjb2RlPkdUQUMuLi4uLi4uPFwvY29kZT5cdWI5N2MgXHViOWNjXHViNGUwXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5UXHVjNzU4IFx1Yzc3Y1x1YmQ4MFx1Yzc3OCBUQVx1Yjk3YyBcdWJjZjVcdWMwYWNcdWQ1NzRcdWMxMWMgPGNvZGU+R1RBQy4uLlRBLi48XC9jb2RlPlx1Yjk3YyBcdWI5Y2NcdWI0ZTBcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlRcdWM1ZDBcdWMxMWMgVEFcdWI5N2MgXHViY2Y1XHVjMGFjXHVkNTVjIFx1YjJlNFx1Yzc0YyBcdWI0YTRcdWM5ZDFcdWM1YjRcdWMxMWMgXHViZDk5XHVjNWVjXHVjMTFjIDxjb2RlPkdUQUMuLi5UQUFUPFwvY29kZT5cdWI5N2MgXHViOWNjXHViNGUwXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMsIFRcdWM3NTggXHVjNzdjXHViZDgwXHVjNzc4IEFBVFx1Yjk3YyBcdWJjZjVcdWMwYWNcdWQ1NzQgPGNvZGU+R1RBQ0FBVFRBQVQ8XC9jb2RlPlx1Yjk3YyBcdWI5Y2NcdWI0ZTBcdWIyZTQuPFwvbGk+XHJcbjxcL29sPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggdFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgdCAmbGU7IDEwMCkgXHViMmU0XHVjNzRjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjQgU1x1YWMwMCwgXHVhZGY4IFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1YmFhOFx1YjQ1MCAxXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDE4XHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFRcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWJjZjVcdWMwYWMgXHVkNjlmXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWJkODhcdWFjMDBcdWIyYTVcdWQ1NWMgXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0ICZxdW90O2ltcG9zc2libGUmcXVvdDtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjUwNTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb3B5aW5nIEROQSIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jb3B5ZG5hLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoyMjlweDsgd2lkdGg6MTM3cHhcIiBcLz5Fdm9sdXRpb24gaXMgYSBzZWVtaW5nbHkgcmFuZG9tIHByb2Nlc3Mgd2hpY2ggd29ya3MgaW4gYSB3YXkgd2hpY2ggcmVzZW1ibGVzIGNlcnRhaW4gYXBwcm9hY2hlcyB3ZSB1c2UgdG8gZ2V0IGFwcHJveGltYXRlIHNvbHV0aW9ucyB0byBoYXJkIGNvbWJpbmF0b3JpYWwgcHJvYmxlbXMuIFlvdSBhcmUgbm93IHRvIGRvIHNvbWV0aGluZyBjb21wbGV0ZWx5IGRpXHVmYjAwZXJlbnQuPFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgRE5BIHN0cmluZyBTIGZyb20gdGhlIGFscGhhYmV0IHtBLEMsRyxUfSwgXHVmYjAxbmQgdGhlIG1pbmltYWwgbnVtYmVyIG9mIGNvcHkgb3BlcmF0aW9ucyBuZWVkZWQgdG8gY3JlYXRlIGFub3RoZXIgc3RyaW5nIFQuIFlvdSBtYXkgcmV2ZXJzZSB0aGUgc3RyaW5ncyB5b3UgY29weSwgYW5kIGNvcHkgYm90aCBmcm9tIFMgYW5kIHRoZSBwaWVjZXMgb2YgeW91ciBwYXJ0aWFsIFQuIFlvdSBtYXkgcHV0IHRoZXNlIHBpZWNlcyB0b2dldGhlciBhdCBhbnkgdGltZS4gWW91IG1heSBvbmx5IGNvcHkgY29udGlndW91cyBwYXJ0cyBvZiB5b3VyIHBhcnRpYWwgVCwgYW5kIGFsbCBjb3BpZWQgc3RyaW5ncyBtdXN0IGJlIHVzZWQgaW4geW91ciBcdWZiMDFuYWwgVC4gRXhhbXBsZTogRnJvbSBTID0gJmxkcXVvO0FDVEcmcmRxdW87IGNyZWF0ZSBUID0gJmxkcXVvO0dUQUNUQVRUQVRBJnJkcXVvOzxcL3A+XHJcblxyXG48b2w+XHJcblx0PGxpPkdldCA8Y29kZT5HVC4uLi4uLi4uLjxcL2NvZGU+IGJ5IGNvcHlpbmcgYW5kIHJldmVyc2luZyAmbGRxdW87VEcmcmRxdW87IGZyb20gUy48XC9saT5cclxuXHQ8bGk+R2V0IDxjb2RlPkdUQUMuLi4uLi4uPFwvY29kZT4gYnkgY29weWluZyAmbGRxdW87QUMmcmRxdW87IGZyb20gUy48XC9saT5cclxuXHQ8bGk+R2V0IDxjb2RlPkdUQUMuLi5UQS4uPFwvY29kZT4gYnkgY29weWluZyAmbGRxdW87VEEmcmRxdW87IGZyb20gdGhlIHBhcnRpYWwgVC48XC9saT5cclxuXHQ8bGk+R2V0IDxjb2RlPkdUQUMuLi5UQUFUPFwvY29kZT4gYnkgY29weWluZyBhbmQgcmV2ZXJzaW5nICZsZHF1bztUQSZyZHF1bzsgZnJvbSB0aGUgcGFydGlhbCBULjxcL2xpPlxyXG5cdDxsaT5HZXQgPGNvZGU+R1RBQ0FBVFRBQVQ8XC9jb2RlPiBieSBjb3B5aW5nICZsZHF1bztBQVQmcmRxdW87IGZyb20gdGhlIHBhcnRpYWwgVC48XC9saT5cclxuPFwvb2w+XHJcbiIsImlucHV0IjoiPHA+VGhlIFx1ZmIwMXJzdCBsaW5lIG9mIGlucHV0IGdpdmVzIGEgc2luZ2xlIGludGVnZXIsIDEgJmxlOyB0ICZsZTsgMTAwLCB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIFRoZW4gZm9sbG93LCBmb3IgZWFjaCB0ZXN0IGNhc2UsIGEgbGluZSB3aXRoIHRoZSBzdHJpbmcgUyBvZiBsZW5ndGggMSAmbGU7IG0gJmxlOyAxOCwgYW5kIGEgbGluZSB3aXRoIHRoZSBzdHJpbmcgVCBvZiBsZW5ndGggMSAmbGU7IG4gJmxlOyAxOC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgZm9yIGVhY2ggdGVzdCBjYXNlIHRoZSBudW1iZXIgb2YgY29weSBvcGVyYXRpb25zIG5lZWRlZCB0byBjcmVhdGUgVCBmcm9tIFMsIG9yICZsZHF1bztpbXBvc3NpYmxlJnJkcXVvOyBpZiBpdCBjYW5ub3QgYmUgZG9uZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=