Evil Straw Warts Live

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

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

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

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

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