티켓 문제

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

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

친구들은 콘서트 당일 매표소에 가서 실제 좌석 번호가 무엇인지 알아볼 것이지만, 지금으로서는 알 수 없다! 티켓에 인쇄된 쌍이 주어졌을 때, 실제로 같은 번호의 행에 모두 앉을 수 있는 친구 수의 최댓값은 얼마인가? (친구들은 그 행에서 연속된 좌석에 앉을 필요는 없다.)

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스는 두 정수 F와 S가 있는 한 줄로 시작하며, 이는 친구 수와 좌석 격자의 크기를 나타낸다. 그 다음 F개의 줄이 이어진다. 그 중 i번째 줄에는 두 정수 Ai와 Bi가 있으며, 이는 i번째 친구의 티켓에 인쇄된 두 숫자를 나타낸다.

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

• F ≤ S2.
• 모든 i에 대해 1 ≤ Ai ≤ Bi ≤ S.
• 한 테스트 케이스에서 같은 쌍이 두 번 이상 나타나지 않는다.
• 같은 숫자가 두 번 포함된 쌍은 한 테스트 케이스에서 두 번 이상 나타나지 않는다.

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

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

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