ASLRDR

공장에 N개의 스테이션이 있는 조립 라인이 있다고 하자. 각 스테이션에서 작업자는 제품에 작업을 수행하는데, 이 작업은 이전 스테이션이나 다음 스테이션의 작업과 같을 수도 있다. 스테이션들의 순서 자체는 중요하지 않지만, 제품이 라인의 한쪽(왼쪽 또는 오른쪽)에서 들어와 반대쪽(오른쪽 또는 왼쪽)으로 나가야 하며 라인 안에서 역방향 이동이 없어야 한다. 이 규칙을 만족하도록 기존 조립 라인을 재배치하는 프로그램을 작성하라. 재배치는 여러 번의 “스테이션 교환”으로 할 수 있지만, 인접한 두 스테이션만 교환할 수 있다.

입력의 첫째 줄은 조립 라인의 수(테스트 케이스의 수) n을 준다.

각 테스트 케이스마다 한 줄이 주어지며, 스테이션들의 이름인 최대 100자의 글자나 숫자로 이루어진 문자열이 들어 있다.

출력은 테스트 케이스마다 한 줄이다. 이 줄에는 가능한 최소 교환 횟수를 출력하거나, 규칙을 만족하도록 스테이션을 재배치할 수 없으면 “Impossible”을 출력한다.

예를 들어, 2, a, D라는 세 작업이 현재 조립 라인에서 “2a2aD” 순서로 있다고 하자. 이 규칙을 만족하려면 “2aDa2”로 재배치해야 하며, 다음과 같이 3번 교환하면 된다:

• “aD”를 교환하여 “2a2Da”를 얻는다.
• “2D”를 교환하여 “2aD2a”를 얻는다.
• “2a”를 교환하여 “2aDa2”를 얻는다.