Reykjavík Random 17

#### Start

2022-01-06 10:00 AKST

## Reykjavík Random 17

#### End

2022-01-13 10:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -139 days 13:33:38

168:00:00

0:00:00

# Problem EEvil Straw Warts Live

A palindrome is a string of symbols that is equal to itself when reversed. Given an input string, not necessarily a palindrome, compute the number of swaps necessary to transform the string into a palindrome. By swap we mean reversing the order of two adjacent symbols. For example, the string “mamad” may be transformed into the palindrome “madam” with 3 swaps:
• swap “ad” to yield “mamda”

• swap “md” to yield “madma”

• swap “ma” to yield “madam”

## Input

The first line of input gives $1 \le n \le 200$, the number of test cases. For each test case, one line of input follows, containing a string of up to $100$ lowercase letters.

## Output

Output consists of one line per test case. This line will contain the number of swaps, or “Impossible” if it is not possible to transform the input to a palindrome.

Sample Input 1 Sample Output 1
3
asflkj
aabb

3
Impossible
2