셰프는 일직선으로 놓인 개의 고기를 고르게 구우려고 한다. 고기에는 왼쪽부터 의 번호가 붙어 있으며, 처음에 모든 고기의 굽기 정도는 이다.
한 번의 작업으로 왼쪽 또는 오른쪽을 선택하고, 정수 화력 ()를 정한다. 선택한 쪽에서 번째에 있는 고기의 굽기 정도는 만큼 증가한다. 선택한 쪽의 맨 끝 고기는 이다.
예를 들어, 고기가 개이고 왼쪽부터 각 고기의 굽기 정도가 이라고 하자. 왼쪽에서 화력 으로 가열하면 굽기 정도가 차례로 만큼 증가하여 이 된다. 이때 네 번째 고기의 굽기 정도는 증가하지 않는다.
이어서 왼쪽에서 화력 로 한 번 더 가열하면, 현재 굽기 정도에 각각 가 더해져 가 된다. 즉, 각 작업에서 증가하는 굽기 정도는 기존 값에 누적된다.
모든 고기의 굽기 정도를 같은 양의 정수로 만들기 위한 최소 작업 횟수와, 이를 달성하는 작업들을 구하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 첫째 줄에 최소 작업 횟수 를 출력한다.
다음 개의 줄에 걸쳐 작업을 수행할 순서대로 출력한다. 번째 줄에는 두 정수 를 공백으로 구분하여 출력한다 ().
첫 번째 테스트 케이스에서는 유일한 고기의 굽기 정도가 이 된다.
두 번째 테스트 케이스에서는 두 고기의 굽기 정도가 모두 이 된다.
세 번째 테스트 케이스에서는 첫 작업 후 굽기 정도가 이고, 두 번째 작업 후 가 된다.
는 테스트 케이스의 개수이다. 각 테스트 케이스는 다음과 같은 형식으로 주어진다.
모든 작업을 수행한 뒤 모든 고기의 굽기 정도는 같고 이상이어야 한다. 가능한 정답이 여러 가지라면 아무거나 하나 출력한다.
