문제

하노이의 탑은 1883년 프랑스의 수학자 에두아르드 뤼카가 처음으로 발표한 게임으로, 3개의 기둥과 여러 개의 원반을 가지고 하는 게임입니다. 이 문제는 하노이의 탑과 비슷하게 3개의 큐(Queue)와 개의 정수가 주어집니다.

세 개의 큐 , , 가 있습니다. 처음에 큐 에는 앞에서부터 개의 정수 가 들어 있으며, 나머지 두 개의 큐는 비어 있습니다. 여러분은 아래 작업을 번 이상 반복할 수 있습니다.

• 서로 다른 두 큐 와 를 선택합니다. 는 비어 있지 않아야 합니다.
• 큐 의 맨 앞에 있는 원소를 큐 의 맨 뒤로 옮깁니다.

큐 의 원소 가 주어질 때, 여러분은 최대 번 작업을 반복한 후에 아래 조건이 성립하도록 하는 방법을 찾아야 합니다.

• 세 개의 큐 중 두 개는 비어 있으며, 나머지 하나의 큐 에는 개의 정수가 들어 있어야 합니다.
• 의 원소를 앞에서부터 순서대로 나열했을 때, 값이 더 작은 원소는 반드시 값이 더 큰 원소보다 앞에 옵니다.

문제의 조건에 따라 그러한 방법이 언제나 존재함을 증명할 수 있습니다.

제한

• 은 의 거듭제곱입니다.
• 모든 테스트 케이스에서 의 합은 이하입니다.

서브태스크

입력

각 입력은 여러 개의 테스트 케이스로 구성됩니다. 첫 번째 줄에 테스트 케이스의 개수 가 주어집니다.

그다음 줄부터 총 개의 테스트 케이스가 개의 줄에 걸쳐 주어집니다.

각 테스트 케이스는 아래와 같이 두 줄로 구성됩니다.

• 첫 번째 줄에 큐 의 원소의 개수 과 작업의 최대 횟수 이 공백으로 구분되어 주어집니다.
• 두 번째 줄에 큐 의 원소 이 공백으로 구분되어 주어집니다.

출력

각 테스트 케이스마다 아래와 같이 최대 두 개의 줄을 출력합니다.

• 첫 번째 줄에 사용한 연산의 횟수 를 출력합니다.
• 두 번째 줄에 각 작업에 대응되는 문자열 개를 공백으로 구분하여 출력합니다. 각 문자열은 작업에서 선택한 서로 다른 두 큐 와 의 이름을 공백 없이 붙인 것과 같습니다. 예를 들어 큐 를 로, 큐 를 로 선택했다면 출력할 문자열은 AB입니다.

단, 이라면 두 번째 줄을 출력하지 않아도 됩니다.

는 반드시 이하여야 하지만 를 최소화할 필요는 없습니다.