개의 구역이 원형으로 연결되어 있다. 구역에는 부터 까지 번호가 붙어 있으며, 번 구역과 번 구역 (), 그리고 번 구역과 번 구역이 서로 인접한다. 처음에는 모든 구역에 바이러스가 퍼져 있다.
매일 정오에 서로 다른 세 구역을 선택하여 그 구역의 바이러스를 제거한다. 이미 바이러스가 없는 구역을 선택해도 된다.
매일 자정에는 바이러스가 인접한 구역으로 동시에 퍼진다. 즉, 자정 직전에 자신 또는 인접한 구역 중 하나 이상에 바이러스가 있었다면 자정 직후 그 구역에 바이러스가 있게 된다. 같은 자정에 새로 감염된 구역에서 바이러스가 다시 퍼지지는 않는다.
일 이내에 모든 구역의 바이러스를 제거하는 방법을 하나 구하여라. 사용한 일수를 최소화할 필요는 없다.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 다음과 같이 출력한다.
첫째 줄에 바이러스를 모두 제거하는 데 사용할 일수 ()를 출력한다.
다음 개의 줄 중 번째 줄에, 일째 정오에 바이러스를 제거할 서로 다른 세 구역의 번호 ()를 공백으로 구분하여 출력한다.
첫째 줄의 는 테스트 케이스의 수이다. 각 케이스는 다음과 같은 형식으로 주어진다.
일째 자정의 전파까지 끝난 뒤 모든 구역에 바이러스가 없어야 한다. 가능한 방법이 여러 가지라면 아무거나 출력해도 된다.
