용으로 싸우기

당신은 탐욕스러운 기사로부터 자신의 둥지를 지키기 위해 싸우는 친절한 용이다! 당신의 체력은 $H_{d}$이고 공격력은 $A_{d}$이며, 기사의 체력은 $H_{k}$이고 공격력은 $A_{k}$이다. 어느 시점에든 당신의 체력이 0 이하로 떨어지면 쓰러져 즉시 패배하며, 어느 시점에든 기사의 체력이 0 이하로 떨어지면 기사가 쓰러져 당신이 승리한다!

당신은 여러 턴에 걸쳐 기사와 전투한다. 각 턴에는 당신이 먼저 행동하며, 다음 행동 중 하나를 골라 실행할 수 있다.

• 공격: 자신의 공격력만큼 상대의 체력을 감소시킨다.

• 강화: 남은 전투 동안 자신의 공격력을 B만큼 증가시킨다.

• 치료: 자신의 체력이 $H_{d}$이 된다.

• 약화: 남은 전투 동안 상대의 공격력을 D만큼 감소시킨다. 약화로 인해 상대의 공격력이 0보다 작아지게 된다면, 대신 공격력을 0로 설정한다.

그런 다음, 당신의 행동 이후 기사의 체력이 0보다 크면 기사가 공격 행동을 실행한다. 그 후 턴이 끝난다. (기사를 쓰러뜨린 턴에는 기사가 행동하지 못하더라도 그 턴은 여전히 하나의 턴으로 센다는 점에 유의하라.)

강화 효과는 서로 누적된다는 점에 유의하라. 강화할 때마다 자신의 공격력에 B가 추가된다. 마찬가지로 약화 효과도 서로 누적된다.

오늘 밤 축제에서 마을 사람들이 마시멜로를 굽는 일을 도우러 늦지 않도록, 가능하다면 최대한 빨리 기사를 쓰러뜨리고 싶다. 기사를 쓰러뜨리는 데 필요한 최소 턴 수를 구하거나, 그렇게 하는 것이 IMPOSSIBLE인지 판별할 수 있는가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100.

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

시간 제한: 60초. 1 ≤ $H_{d}$ ≤ 100. 1 ≤ $A_{d}$ ≤ 100. 1 ≤ $H_{k}$ ≤ 100. 1 ≤ $A_{k}$ ≤ 100. 0 ≤ B ≤ 100. 0 ≤ D ≤ 100.

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

시간 제한: 240초. 1 ≤ $H_{d}$ ≤ $10^{9}$. 1 ≤ $A_{d}$ ≤ $10^{9}$. 1 ≤ $H_{k}$ ≤ $10^{9}$. 1 ≤ $A_{k}$ ≤ $10^{9}$. 0 ≤ B ≤ $10^{9}$. 0 ≤ D ≤ $10^{9}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 위에서 설명한 여섯 정수 $H_{d}$, $A_{d}$, $H_{k}$, $A_{k}$, B, D가 한 줄에 주어진다.

각 테스트 케이스마다 Case #x: y을 한 줄에 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 기사를 쓰러뜨릴 수 없다면 IMPOSSIBLE이며, 그렇지 않으면 기사를 쓰러뜨리는 데 필요한 최소 턴 수이다.

케이스 #1에서 당신의 체력은 11이고 공격력은 5이며, 기사의 체력은 16이고 공격력은 5이다. 가능한 최적 행동 순서 중 하나는 다음과 같다.

• 턴 1: 공격하여 기사의 체력을 11로 감소시킨다. 그러면 기사가 공격하여 당신의 체력을 6으로 감소시킨다.

• 턴 2: 공격하여 기사의 체력을 6로 감소시킨다. 그러면 기사가 공격하여 당신의 체력을 1으로 감소시킨다.

• 턴 3: 치료하여 자신의 체력을 11으로 회복한다. 그러면 기사가 공격하여 당신의 체력을 6으로 감소시킨다. (이 턴에 대신 공격했다면 기사의 다음 공격으로 인해 패배했을 것이다.)

• 턴 4: 공격하여 기사의 체력을 1로 감소시킨다. 그러면 기사가 공격하여 당신의 체력을 1으로 감소시킨다.

• 턴 5: 공격하여 기사의 체력을 -4로 감소시킨다. 당신은 즉시 승리하며 기사는 다시 공격하지 못한다.

케이스 #2에서 가능한 최적 행동 순서 중 하나는 다음과 같다.

• 턴 1: 강화하여 자신의 공격력을 3로 증가시킨다. 그러면 기사가 공격하여 당신의 체력을 1로 감소시킨다.

• 턴 2: 공격하여 기사의 체력을 0로 감소시킨다. 당신은 즉시 승리하며 기사는 다시 공격하지 못한다.

케이스 #3에서 기사는 단 두 번의 공격만으로 당신을 쓰러뜨릴 수 있으며, 당신은 기사를 쓰러뜨릴 만큼 충분한 피해를 빠르게 줄 수 없다. 매번 공격한 뒤 치료 행동을 실행하여 전투를 무한히 연장할 수는 있지만, 실제로 기사를 쓰러뜨리는 것은 불가능하다.

케이스 #4에서 가능한 최적 행동 순서 중 하나는 공격, 약화, 강화, 공격, 공격이다.