관광

여행을 할 때 가능한 한 많은 도시에서 관광을 하며 시간을 보내고 싶지만, 다음 도시로 가는 버스를 타야 하기 때문에 그러지 못할 때도 있다. 여행의 즐거움을 최대한으로 하기 위해 일정을 최적화하는 프로그램을 작성하기로 했다.

도시 1에서 시각 0에 출발해 도시 2부터 N까지 오름차순으로 모든 도시를 방문할 계획이다. 모든 도시 i에서 다음 도시 i + 1로 가는 버스편이 있다. i번째 버스편은 시작 시각, 주기, 이동 시간을 나타내는 3개의 정수 Si, Fi, Di로 주어지는 운행 일정을 따른다. 정확히 말하면, 도시 i에서 시각 Si + xFi (x는 정수, x ≥ 0)마다 버스가 출발하며, 그 버스는 도시 i + 1까지 Di의 시간이 걸린다.

도시 1부터 N - 1까지 각 도시에서 다음 버스를 기다리기 전에 Ts만큼 관광을 하며 시간을 보낼지, 아니면 곧바로 다음 버스를 기다릴지 정할 수 있다. 같은 도시에서 관광을 여러 번 할 수는 없다. 버스에 타고 내리는 데는 시간이 걸리지 않는다고 가정한다. 도시 N에는 늦어도 시각 Tf까지 도착해야 한다. (도시 N에서는 일찍 도착하더라도 관광을 할 수 없다. 볼 것이 없다!)

관광을 할 수 있는 도시의 최대 개수는 얼마인가?

입력은 첫 줄에 테스트 케이스의 수 T가 주어지며 시작한다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 도시의 수, 어느 도시에서든 관광에 걸리는 시간, 도시 N에 도착할 수 있는 가장 늦은 시각을 나타내는 3개의 정수 N, Ts, Tf가 있는 한 줄로 시작한다.

이어서 N - 1개의 줄이 주어진다. i번째 줄에는 도시 i에서 도시 i + 1로 가는 버스의 시작 시각, 주기, 이동 시간을 나타내는 3개의 정수 Si, Fi, Di가 있다.

각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 늦어도 시각 Tf까지 도시 N에 도착할 수 있으면서 관광을 할 수 있는 도시의 최대 개수이다. 시각 Tf까지 도시 N에 도착할 수 없다면 Case #x: IMPOSSIBLE을 출력한다.

• 1 ≤ T ≤ 100.