Evil Straw Warts Live

면접 대비

시간 제한1초메모리 제한128 MB

요약

각 문자열을 팰린드롬으로 만들기 위해 필요한 인접 교환의 최소 횟수를 구하고, 불가능하면 Impossible을 출력한다.

난이도: 보통10점 중 5점
유형: 그리디, 투 포인터, 문자열, 구현
정답자: 아직 제출이 없습니다

문제

회문(palindrome)은 앞에서 읽으나 뒤에서 읽으나 똑같은 문자열입니다. 문자열 하나가 주어질 때(회문이 아닐 수도 있습니다), 이 문자열을 회문으로 바꾸는 데 필요한 최소 교환 횟수를 구하세요. 여기서 한 번의 교환이란 인접한 두 문자의 순서를 서로 뒤바꾸는 것을 말합니다.

예를 들어 문자열 "mamad"는 세 번의 교환으로 회문 "madam"이 됩니다.

"ad"를 교환하여 "mamda"
"md"를 교환하여 "madma"
"ma"를 교환하여 "madam"

입력

첫 번째 줄에 테스트 케이스의 수 $n$ 이 주어집니다. 이어서 각 테스트 케이스마다 한 줄씩, 소문자 알파벳으로 이루어진 길이 최대 $100$ 의 문자열이 주어집니다.

출력

각 테스트 케이스마다 한 줄씩, 회문으로 만드는 데 필요한 최소 교환 횟수를 출력합니다. 회문으로 만들 수 없는 경우에는 "Impossible"을 출력합니다.

예제4

예제 1
입력
```
3
mamad
asflkj
aabb
```
예상 출력
```
3
Impossible
2
```
예제 2
입력
```
2
racecar
a
```
예상 출력
```
0
0
```
예제 3
입력
```
2
ab
abb
```
예상 출력
```
Impossible
1
```
예제 4
입력
```
3
abba
noon
aaaa
```
예상 출력
```
0
0
0
```