gFiles

외계 기술 기업 G에는 현재도 사용 중인 매우 오래된 파일 전송 도구가 있다. 이 도구는 실행되는 동안 지금까지 전송된 파일의 비율과 지금까지 전송된 파일의 수를 모두 상태 업데이트로 알려 사용자를 안심시킨다. 전송 과정의 상태 업데이트는 다음과 같을 수 있다.

20% |==>-------|     1 files transferred
100% |==========|     5 files transferred

하지만 비율은 정확하지 않다. 소수점 앞에서 단순히 잘린다(즉, 그보다 작거나 같은 다음 1%로 내림한다). 다시 말해, 1.2%와 1.7%는 모두 1%로 표시된다.

일부 사용자는 정확한 전체 파일 수를 알고 싶어 할 수 있으므로, 상태 업데이트가 다음과 같이 표시되도록 도구를 수정하려 한다.

20% |==>-------|     1 out of 5 files transferred
100% |==========|     5 out of 5 files transferred

하지만 파일 수를 알아내는 것이 가능할 수도, 가능하지 않을 수도 있다는 사실을 깨달았다. 도구가 표시하는 상태 업데이트가 주어질 때, 파일이 몇 개인지 알아내거나 이를 알아낼 수 없다고 판단하라(즉, 가능한 파일 수가 여러 개이다). 상태 업데이트가 일정한 간격으로 발생한다는 보장은 없으며, 파일이 전송될 때마다 발생한다는 보장도 없다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 50. 1 ≤ N ≤ 100. 0 ≤ $P_{i}$ ≤ 100

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

0 ≤ $K_{i}$ ≤ 2000 답은 2000을 초과하지 않음이 보장된다.

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

0 ≤ $K_{i}$ ≤ $10^{15}$ 답은 $10^{15}$을 초과하지 않음이 보장된다.

첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 도구가 출력한 상태 업데이트의 수를 나타내는 정수 N이 있는 한 줄과, 그 뒤에 $P_{i}$ $K_{i}$ 형식의 N개 줄로 구성된다. 여기서 $P_{i}$와 $K_{i}$는 전송 과정의 어떤 시점에 전송된 파일의 비율과 수를 나타내는 정수이다. 업데이트는 시간순으로 나열되어 주어진다. 즉, 각 테스트 케이스 전체에서 $P_{i}$ 값과 $K_{i}$ 값은 모두 감소하지 않는다.

각 케이스마다 "Case #x: y"로 시작하는 한 줄을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, y는 전체 파일 수이거나 그 수가 모호한 경우 -1이다.