꽃병 수집

정 선생은 오래된 중국 도자기, 그중에서도 15세기 후반 펑(Feng) 왕조의 꽃병을 수집한다. 당시 꽃병 제작은 매우 엄격한 예술 규칙을 따랐다. 꽃병의 모양은 36가지, 장식 무늬는 36가지가 있었고, 따라서 서로 다른 양식은 모두 $36 \times 36 = 1296$가지였다.

수집가라면 1296가지 양식을 하나씩 모두 갖추는 것이 이상적인 목표겠지만, 정 선생도 다른 많은 수집가와 마찬가지로 전부를 모을 형편은 못 되어 일부 모양과 일부 장식에만 집중한다. 펑 왕조 미학에서는 모양과 장식 사이의 대칭이 중요했기에, 정 선생은 가능한 한 큰 $k$에 대해 균형 잡힌 수집을 원한다. 즉, 어떤 $k$개의 모양과 $k$개의 장식을 골랐을 때 그 $k \times k$가지 조합을 모두 소장한 상태를 만들고 싶어 한다.

주어진 수집품에서 이 $k$를 구하는 일은 언제나 쉽지만은 않아서, 그의 수집품은 스스로 생각하는 것보다 더 나을 수도 있다. 정 선생이 가진 꽃병들이 주어질 때, 가능한 가장 큰 $k$를 구하여라.

첫째 줄에 시나리오의 개수를 나타내는 양의 정수 $n$이 주어진다.

각 시나리오의 첫 줄에는 수집품에 들어 있는 꽃병의 수를 나타내는 양의 정수 $m$ ($m \le 100$)이 주어진다. 이어지는 $m$개의 줄에는 꽃병이 하나씩 주어지며, 각 줄에는 공백 하나로 구분된 두 정수 $s_i$와 $d_i$가 있다. $s_i$ ($1 \le s_i \le 36$)는 $i$번째 꽃병의 모양을, $d_i$ ($1 \le d_i \le 36$)는 그 장식을 나타낸다.

각 시나리오마다 한 줄에 최대 $k$를 출력한다. 여기서 $k$는, 수집품이 그 $k \times k$가지 조합 양식을 모두 포함하는 $k$개의 모양과 $k$개의 장식이 존재하도록 하는 가장 큰 값이다.