4M 주식회사

4M 주식회사는 부서를 구성하고 인원을 배정하도록 당신을 고용했다. 당신은 적어도 하나의 부서를 만들며, 각 부서에는 양의 정수 명의 직원이 배정된다. 하지만 쉽지는 않을 것이다. 서로 다른 상사가 네 명 있고, 각 상사는 서로 다른 지시를 내렸다.

• 직원이 가장 적은 부서에는 정확히 MINIMUM명의 직원이 있어야 한다.

• 직원이 가장 많은 부서에는 정확히 MAXIMUM명의 직원이 있어야 한다.

• 모든 부서의 평균 직원 수는 정확히 MEAN이어야 한다.

• 모든 부서의 직원 수의 중앙값은 정확히 MEDIAN이어야 한다. 다시 말해, 목록의 중앙값은 목록을 비내림차순으로 정렬했을 때 중앙에 있는 값(목록의 길이가 홀수인 경우) 또는 중앙에 있는 두 값의 평균(목록의 길이가 짝수인 경우)이다.

또한 효율성을 위해 부서를 너무 많이 만들지 않는 것이 가장 좋다. 상사들의 요구를 충족할 수 있다면, 만들 수 있는 부서 수의 최솟값은 얼마인가?

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB.

작은 데이터 세트(테스트 세트 1 - 공개)

1 ≤ MINIMUM ≤ 8. 1 ≤ MAXIMUM ≤ 8. 1 ≤ MEAN ≤ 8. 1 ≤ MEDIAN ≤ 8. 작은 데이터 세트의 제한 조건은 답이 IMPOSSIBLE이거나 14보다 작음을 보장한다.

큰 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ MINIMUM ≤ 10000. 1 ≤ MAXIMUM ≤ 10000. 1 ≤ MEAN ≤ 10000. 1 ≤ MEDIAN ≤ 10000.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 네 정수 MINIMUM, MAXIMUM, MEAN, MEDIAN로 이루어지며, 이 순서대로 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y은 가능한 최소 부서 수이며, 네 상사의 요구를 모두 충족하는 것이 불가능한 경우에는 IMPOSSIBLE이다.

예제 케이스 #1의 답은 IMPOSSIBLE이다. 최댓값은 최솟값보다 작을 수 없기 때문이다.

예제 케이스 #2의 답은 IMPOSSIBLE이다. 평균과 중앙값은 최댓값보다 클 수 없기 때문이다.

예제 케이스 #3에서는 직원이 2명인 부서 하나를 만들 수 있다. 이는 네 상사를 모두 만족시킨다. 직원이 가장 적은 부서에는 정확히 2명이 있고, 직원이 가장 많은 부서에는 정확히 2명이 있으며, 평균과 중앙값은 모두 2이다.

예제 케이스 #4에서는 직원이 3명인 부서 하나와 직원이 7명인 또 다른 부서 하나를 만들 수 있다. 직원이 5명인 부서 하나만 만드는 것으로는 충분하지 않다는 점에 유의하라. 그렇게 하면 직원이 가장 적은 부서의 직원 수가 정확히 3명이 아니고, 직원이 가장 많은 부서의 직원 수도 정확히 7명이 아니기 때문이다.

예제 케이스 #5에서는 직원이 1명인 부서 하나와 각각 직원이 4명인 부서 두 개를 더 만들 수 있다.