ad gkazalli corsines— Feryquitous, 「Arcahv」
히카리는 개의 조각을 모으려고 한다. 조각은 하늘을 떠다니고 있어 그냥 모을 수 없고, 땅에 떨어진 조각만 모을 수 있다. 처음에 번째 조각의 높이는 이고, 이 되면 히카리는 번째 조각을 있다.
다행히, 히카리에게는 신비한 능력이 있어서 두 조각의 상호작용을 통해 그 중 한 조각의 높이를 낮출 수 있다. 인 서로 다른 두 정수 , 를 골라 능력을 사용할 경우 를 만큼 감소시킬 수 있다.
의 정의
은 일 경우 두 정수 , 을 나머지 없이 나눌 수 있는 가장 큰 양의 정수로 정의하며, 그 외에는 으로 정의한다.
하지만, 능력을 너무 많이 사용하면 타이리츠에게 들키기 때문에 최대 번 이하로 능력을 사용해서 모든 조각을 땅으로 떨어뜨려야 한다.
히카리를 위해서 번 이하로 능력을 사용해서 모든 조각을 땅으로 떨어뜨리는 방법을 아무거나 하나 찾아야 한다. 그러한 방법이 주어진 제약조건 하에 항상 존재한다는 것을 증명 가능하다. 능력을 사용하는 횟수를 최소화할 필요는 없다.
첫 번째 줄에 테스트 케이스의 개수 가 주어진다.
각 테스트 케이스의 첫 번째 줄에 히카리가 모아야 하는 조각의 개수 이 주어진다.
각 테스트 케이스의 두 번째 줄에 각 조각의 높이를 나타내는 개의 정수 이 공백을 사이에 두고 주어진다.
모든 테스트 케이스의 의 총합은 을 넘지 않는다.
각 테스트 케이스에 대해, 첫 번째 줄에 사용한 능력의 횟수 를 출력한다.
다음 개의 줄 중 번째 줄에 번째로 능력을 사용할 때 선택한 를 공백을 사이에 두고 출력한다.
가능한 정답이 여러 가지라면 그 중 아무거나 하나 출력한다.
