Vase Collection

Mr. Cheng collects old Chinese porcelain, and in particular late-15th-century Feng dynasty vases. Vase-making of that era followed very strict artistic rules. There were exactly 36 shapes and 36 decoration patterns, giving $36 \times 36 = 1296$ distinct styles in all.

The obvious goal for a collector is to own one sample of every one of the 1296 styles. Like most collectors, however, Mr. Cheng can never afford a complete collection, so he concentrates on some shapes and some decorations. Because symmetry between shape and decoration was a central aesthetic principle of the Feng dynasty, Mr. Cheng wants the largest possible balanced sub-collection: for as large a $k$ as possible, he wants a set of $k$ shapes and $k$ decorations such that his collection contains all $k \times k$ combined styles of those shapes and decorations.

Determining this $k$ for a given collection is not always easy, which means his collection might actually be better than he thinks. Given the vases he owns, help him find the largest such $k$.

The first line contains a single positive integer $n$, the number of test scenarios that follow.

Each scenario begins with a line containing a single positive integer $m$ ($m \le 100$), the number of vases in the collection. Then follow $m$ lines, one per vase, each containing two integers $s_i$ and $d_i$ separated by a single space, where $s_i$ ($1 \le s_i \le 36$) is the shape of the $i$-th vase and $d_i$ ($1 \le d_i \le 36$) is its decoration.

For each scenario, output one line containing the maximum $k$ such that there exist $k$ shapes and $k$ decorations for which the collection contains all $k \times k$ combined styles.