티켓 소동

F명의 친구가 원형극장에서 열리는 회의에 참석하고 있으며, 이후 그곳에서 열리는 콘서트를 보기 위한 티켓을 샀다. 원형극장의 좌석은 S개의 행과 S개의 열로 이루어진 격자 형태이다. 원형극장은 각 좌석에 대해 한 장의 티켓을 판매했다(그중 일부는 이 친구들에게 판매되지 않았을 수도 있다). 각 티켓에는 일반적으로 한 좌석의 행 번호와 열 번호를 나타내는 정수 쌍이 그 순서대로 적혀 있다. 예를 들어 티켓에 일반적으로 (2, 1)라고 적혀 있다면 이는 2행, 1열을 의미하고, (2, 2)라고 적혀 있다면 2행, 2열을 의미한다.

티켓을 인쇄할 때 오작동이 발생하여 각 쌍의 두 수가 항상 정렬된(즉, 비감소하는) 순서로 인쇄되었다! 따라서 예를 들어 (1, 2)라고 적힌 티켓은 실제로 1행, 2열의 좌석에 대한 것일 수도 있고, 실제로 2행, 1열의 좌석에 대한 것일 수도 있다. 두 친구의 티켓에 (1, 2)라고 적혀 있다면, 하나는 실제로 1행, 2열에 대한 것이어야 하고 다른 하나는 실제로 2행, 1열에 대한 것이어야 한다.

친구들은 콘서트 당일 매표소에 문의하여 실제 좌석 번호를 알아낼 예정이지만, 지금은 확실하지 않다! 티켓에 인쇄된 쌍이 주어질 때, 실제로 모두 같은 번호의 좌석 행에 앉을 수 있는 친구 수의 가능한 최댓값은 얼마인가? (친구들이 그 행에서 반드시 연속된 좌석에 앉을 필요는 없다.)

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. F ≤ $S^{2}$. 모든 i에 대해 1 ≤ $A_{i}$ ≤ $B_{i}$ ≤ S이다. 하나의 테스트 케이스에서 같은 쌍은 두 번을 초과하여 나타나지 않는다. 하나의 테스트 케이스에서 같은 수를 두 번 포함하는 쌍은 한 번을 초과하여 나타나지 않는다.

소규모 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ T ≤ 50. 2 ≤ F ≤ 3. 2 ≤ S ≤ 3.

대규모 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ T ≤ 100. 2 ≤ F ≤ 100. 2 ≤ S ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 친구 수와 좌석 격자의 한 변 길이를 나타내는 두 정수 F와 S가 있는 한 줄로 시작한다. 그다음 F개의 줄이 더 주어진다. 그중 i번째 줄에는 i번째 친구의 티켓에 인쇄된 두 수를 나타내는 두 정수 $A_{i}$와 $B_{i}$이 주어진다.

각 테스트 케이스마다 Case #x: y을 담은 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작), y은 실제로 모두 같은 번호의 좌석 행에 앉을 수 있는 친구 수의 가능한 최댓값이다.

예제 케이스 #1에서 한 티켓은 실제로 1행, 2열에 대한 것이어야 하고, 다른 티켓은 실제로 2행, 1열에 대한 것이어야 하지만, 어느 것이 어느 것인지는 알 수 없다. 따라서 친구들이 같은 행에 앉지 않는다는 것을 알 수 있으며, 어느 행에서든 친구 수의 최댓값은 1이다. 또한 좌석에는 세 번째 행과 열도 있지만 어떤 티켓도 세 번째 행이나 열을 사용하지 않는다는 점에 유의하라.

예제 케이스 #2에서 티켓 중 하나는 확실히 2행의 좌석 2에 대한 것이며, 다른 티켓 중 두 개가 2행의 좌석 1과 3에 대한 것일 수도 있다. 따라서 같은 행에 최대 3명의 친구가 있을 수 있다.

예제 케이스 #3에서는 1행에 친구 두 명이 있고 2행에 한 명이 있거나, 2행에 친구 두 명이 있고 1행에 한 명이 있다. 어느 경우든 답은 2이다.