하키 점수

휴 하키(Hugh Hockey)는 열성적인 하키 팬입니다. 토요일 밤마다 자리에 앉아 모든 하키 경기를 빠짐없이 시청하며 단 한 순간도 놓치려 하지 않습니다.

그런데 이번 토요일 밤은 다릅니다. 휴에게 데이트 약속이 생겼기 때문입니다. 그래서 그는 세 살배기 동생 빌리(Billy)에게 대신 점수를 적게 했습니다. 빌리를 TV 앞에 앉히고 채널 바꾸는 법을 가르쳐 준 뒤 하키 점수를 받아 적으라고 부탁했습니다.

데이트를 마치고 돌아온 휴는 뜻밖의 상황을 마주합니다. 빌리는 점수는 적었지만 어느 팀의 점수인지 팀 이름은 적지 않았습니다. 또한 최종 점수뿐 아니라 진행 중이던 경기의 중간 점수까지 함께 적어 두었습니다. 게다가 빌리는 한 점수를 적을 때 일정한 순서를 지키지 않아서, 2 대 1 점수가 2-1로 적혔을 수도, 1-2로 적혔을 수도 있습니다. 빌리가 모든 점수를 빠짐없이 적었다는 보장도 없어 일부 점수는 누락되었을 수 있습니다.

하키 경기에서 점수는 0-0에서 시작하며 결코 줄어들지 않습니다. 골이 나면 한 팀의 점수가 1 늘어날 뿐입니다. 따라서 한 경기가 진행되는 동안 두 팀의 점수는 시간이 지나면서 증가하기만 합니다. 빌리는 어느 팀이 어느 팀인지 적지 않았으므로, 적힌 점수 x-y는 어떤 순간 두 팀의 점수가 (순서에 상관없이) x와 y인 경기의 그 순간과 일치합니다. 한 경기가 빌리가 적은 여러 점수를 설명할 수 있습니다.

빌리의 목록을 보고, 빌리가 적은 모든 점수가 어떤 경기의 어떤 순간에 나타나도록 하려면 최소 몇 경기가 열렸어야 하는지 구해 휴를 도와주세요.

입력은 여러 개의 테스트 케이스로 이루어집니다. 첫 줄에는 테스트 케이스의 수를 나타내는 정수 $n$이 주어집니다.

각 테스트 케이스의 첫 줄에는 빌리가 적은 점수의 개수를 나타내는 정수 $s$ ($1 \leq s \leq 1000$)가 주어집니다. 이어지는 $s$개의 줄에는 각각 x-y 형태의 점수가 하나씩 주어지며, 여기서 $x$와 $y$는 음이 아닌 정수입니다.

각 테스트 케이스마다, 빌리가 적은 모든 점수가 어떤 경기의 어떤 순간에 나타나도록 하는 데 필요한 최소 경기 수 $m$을 한 줄에 출력합니다.

서로 같은 점수 — 예컨대 2-1과 1-2처럼 순서만 뒤바뀐 것 — 는 같은 점수를 가리키며 추가 경기를 요구하지 않습니다.