장난감

어린 Axel에게는 1부터 N까지 번호가 매겨진 N개의 장난감이 있다. 각 장난감에는 두 가지 속성이 있다:

• $E_{i}$—즐거움으로, Axel이 장난감 번호 i에 싫증 나지 않고 가지고 놀 수 있는 시간(분)이다;

• $R_{i}$—기억 지속 시간으로, Axel이 장난감 번호 i를 가지고 논 뒤 그 장난감을 잊는 데 걸리는 시간(분)이다.

장난감들은 1부터 N까지 시계 방향으로 원형으로 배치되어 있다. Axel은 장난감을 하나씩 가지고 논다.

Axel이 아직 가지고 놀지 않았거나 이미 잊은 장난감 i에 도달하면, 그 장난감을 $E_{i}$분 동안 가지고 논 다음 즉시 다음 장난감으로 이동한다(시계 방향).

아직 잊지 않은 장난감에 도달하면(마지막으로 그 장난감을 가지고 노는 것을 마친 뒤 $R_{i}$분보다 적은 시간이 지났다면), 그는 멈추고 울 것이다.

Axel이 장난감을 가지고 논 시간은 멈추기 전에 가지고 논 모든 장난감의 $E_{i}$의 합으로 정의할 수 있다. Axel이 어떤 장난감을 여러 번 가지고 놀았다면, 가지고 논 횟수만큼 합에 포함해야 한다.

장난감에 대한 설명이 주어질 때, Axel이 무한히 오랫동안 놀 수 있게 하거나, 그것이 불가능하다면 멈추기 전까지 가능한 한 오랫동안 놀 수 있게 하기 위해 장난감을 가능한 한 적게 제거한다.

참고:

• Axel은 이전에 이 장난감들을 가지고 논 적이 없다;

• 장난감이 하나도 남지 않게 할 수는 없다;

• 항상 번호가 가장 작은 장난감부터 시작한다;

• 번호가 가장 큰 장난감을 가지고 노는 것을 마친 뒤에는 번호가 가장 작은 장난감으로 이동한다.

제한

시간 제한: 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ $E_{i}$ ≤ $10^{9}$. 1 ≤ $R_{i}$ ≤ $10^{9}$.

테스트 세트 1

1 ≤ N ≤ 12.

테스트 세트 2

1 ≤ N ≤ $10^{5}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 N을 포함하는 줄로 시작한다. 다음 N개의 줄에는 각각 2개의 정수, $E_{i}$와 $R_{i}$이 주어진다. i번째 줄은 장난감 번호 i를 설명한다.

각 테스트 케이스마다 Case #x: y z을 포함하는 한 줄을 출력한다. 여기서:

• x은 테스트 케이스 번호이다(1부터 시작);

• y은 Axel이 놀게 될 가장 긴 시간(분)이며, 무한히 오랫동안 놀게 된다면 "INDEFINITELY"(따옴표 없이)이다.

• z은 Axel이 남은 장난감들을 가지고 무한히 오랫동안 또는 가능한 한 오랫동안 놀 수 있도록 제거해야 하는 장난감의 최소 개수이다;

예제 케이스 #1에는 장난감이 하나뿐이므로, Axel은 그 장난감을 가지고 놀다가 5분 후에 싫증이 날 것이다.

예제 케이스 #2에서 장난감 번호 1을 5분 동안 가지고 논 뒤, 그는 그 장난감을 10분 동안 가지고 놀지 않아야 하며, 그 시간 동안 장난감 번호 2을 가지고 놀 것이다. 그 후 장난감 번호 1으로 돌아가서 5분 동안 가지고 놀며, 그동안 장난감 번호 2을 잊게 되고, 이런 과정이 계속된다. 따라서 그는 무한히 오랫동안 놀 것이다.

예제 케이스 #3에서 Axel은 장난감 번호 1을 30분 동안 가지고 놀 수 있지만, 그 장난감을 제거하면 나머지 장난감들을 가지고 무한히 놀 수 있다. 따라서 그 장난감을 제거하고 다른 두 개를 남긴다.

예제 케이스 #4에서 Axel은 다음 순서로 장난감을 가지고 논다: 1, 2, 3, 1, 2. 그런 다음 장난감 번호 3을 아직 기억하고 있으므로 멈추고 울 것이다. 따라서 그는 총 25분 동안 놀 것이다.