수수께끼의 도로 표지판

Signfield 마을은 서쪽에서 동쪽으로 뻗은 완벽하게 곧고 무한히 긴 도로 위에 있다. 그 도로를 따라 양쪽 면에 숫자가 적힌 S개의 수수께끼 같은 도로 표지판이 차례로 놓여 있다. i번째 표지판(서쪽에서 동쪽으로 순서대로 번호를 매긴다)은 Signfield에서 동쪽으로 $D_{i}$킬로미터 떨어진 지점에 있으며, 서쪽을 향한 면에는 숫자 $A_{i}$이, 동쪽을 향한 면에는 숫자 $B_{i}$가 적혀 있다.

Signfield의 누구도 이 표지판들이 무엇을 말하려는지 알지 못한다. 당신은 표지판의 서쪽 면에 적힌 숫자는 동쪽으로 이동하는 운전자를 위한 것이며, 어떤 특정 목적지까지의 거리를 나타낸다고 생각한다. 마찬가지로 표지판의 동쪽 면에 적힌 숫자는 서쪽으로 이동하는 운전자를 위한 것이며, 어떤 특정 목적지까지의 거리를 나타낸다고 생각한다. 하지만 모든 표지판이 이 이론에 부합하지는 않을 수도 있다고 의심한다.

이 이론을 검증하기 위해, 다음 규칙을 따르는 유효한 표지판 집합을 찾고자 한다.

• 집합은 모든 도로 표지판으로 이루어진 수열의 연속 부분 수열이다. (전체 수열도 연속 부분 수열로 간주한다.)

• Signfield에서 동쪽으로 M킬로미터 및 N킬로미터 떨어진 위치가 존재해야 한다. 여기서 M과 N은 양수일 필요도 없고 서로 다를 필요도 없는 수이며, 그 집합의 모든 표지판에 대해 다음 중 적어도 하나가 참이어야 한다.

• $D_{i}$ + $A_{i}$ = M.

• $D_{i}$ - $B_{i}$ = N.

위에서 설명한 유효한 집합에 포함될 수 있는 표지판 수의 최댓값은 얼마이며, 그 크기를 갖는 서로 다른 유효한 집합은 몇 개인가?

제한

1 ≤ T ≤ 60. 모든 i에 대해 1 ≤ $D_{i}$ ≤ $10^{6}$. 모든 i < j에 대해 $D_{i}$ < $D_{j}$. 모든 i에 대해 1 ≤ $A_{i}$ ≤ $10^{6}$. 모든 i에 대해 1 ≤ $B_{i}$ ≤ $10^{6}$. 시간 제한(각 테스트 세트): 10초. 메모리 제한: 1GB.

테스트 세트 1 (공개)

모든 테스트 케이스에 대해 1 ≤ S ≤ 100.

테스트 세트 2 (비공개)

3개의 테스트 케이스를 제외한 모든 테스트 케이스에 대해 1 ≤ S ≤ 100. 3개의 테스트 케이스에 대해 S = $10^{5}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 도로 표지판의 수를 나타내는 정수 S가 담긴 한 줄로 시작한다. 그다음 S개의 줄이 주어진다. 이 중 i번째 줄은 i번째 표지판(서쪽에서 동쪽으로 나열한 순서)을 나타내며, 세 정수 $D_{i}$, $A_{i}$, $B_{i}$가 주어진다. 이들은 각각 Signfield에서 동쪽으로 떨어진 표지판의 거리(킬로미터 단위), 서쪽 면의 숫자, 동쪽 면의 숫자를 나타낸다.

각 테스트 케이스마다 Case #x: y z을 담은 한 줄을 출력한다. 여기서 x은 1부터 시작하는 테스트 케이스 번호이고, y과 z는 문제 설명에서 정의한 유효한 집합에 포함될 수 있는 표지판 수의 최댓값과 그 크기를 갖는 유효한 집합의 수이다.

예제 케이스 #1에는 표지판이 하나뿐이다. 그 표지판 하나만 집합으로 선택하면 가능한 M과 N의 값은 많다. 예를 들면 다음과 같다.

• M = 2이고 N = 0

• M = 1이고 N = 0 (각 표지판은 두 값 중 하나에 대해서만 올바르면 된다는 점을 기억하라. 또한 M과 N은 하나 이상의 표지판 또는 Signfield 자체와 같은 위치에 있을 수도 있다.)

• M = 2이고 N = -12345 (N은 Signfield의 서쪽에 있을 수도 있다.)

• M = 0이고 N = 0 (M과 N은 서로 다를 필요가 없다.)

• M = 2이고 N = 3 (N은 M의 동쪽에 있을 수도 있다.)

따라서 그 표지판 하나로만 이루어진 집합은 유효하다. 그 길이를 갖는 집합은 이것뿐이므로 답은 1 1이다.

예제 케이스 #2에서 첫 번째, 두 번째, 네 번째, 다섯 번째 표지판은 M = 9이고 N = -1일 때 이론에 부합하지만, 연속 부분 수열을 이루지 않는다는 점에 유의하라. (세 번째 표지판 뒷면의 1을 앞면에 있는 것처럼 사용할 수는 없다.) 실제로 네 개의 표지판으로 이루어진 유효한 집합은 없다. 세 개의 표지판으로 이루어진 서로 다른 유효한 집합은 두 개 있다. 두 번째 표지판 세 개의 집합을 유효하게 만드는 M/N 쌍이 서로 다른 두 개 존재하지만, 그 집합은 한 번만 센다는 점에 유의하라.

• 첫 번째, 두 번째, 세 번째 표지판. M = 9이고 N = 7

• 세 번째, 네 번째, 다섯 번째 표지판. M = 18이고 N = -1이거나, M = 22이고 N = 7

예제 케이스 #3에서는 전체 수열이 유효한 집합이며, M = 4이고 N = 2이다.