题目描述

程先生是中国古代瓷器收藏家，尤其专注于15世纪晚期丰朝的花瓶。该时期的制瓶艺术遵循严格的艺术规范，仅存在有限的公认风格，每种风格由器型和纹饰共同定义。具体来说，共有36种器型和36种纹饰图案，总计1296种不同风格。

对收藏家而言，理想目标是集齐全部1296种风格。但程先生和许多收藏家一样，无力完成完整收藏，因此专注于部分器型和纹饰。由于“器型与纹饰的对称性”是丰朝美学的核心范式，程先生希望找到最大的整数k，使得其收藏中包含k种器型与k种纹饰的所有k×k种组合。然而他发现，确定收藏对应的最大k值并非易事——或许其收藏比想象中更完善。你能帮他计算吗？

输入格式

• 首行包含一个正整数n，表示测试用例的数量。
• 每个测试用例的首行是一个正整数m（m ≤ 100），表示收藏的花瓶数量。
• 接下来m行，每行包含两个整数si和di，分别表示第i个花瓶的器型和纹饰（1 ≤ si, di ≤ 36）。

输出格式

对每个测试用例，输出一行整数k，表示最大的正整数，使得存在k种器型和k种纹饰，其所有k×k种组合均在收藏中。

输入样例

2  
5  
11 13  
23 5  
17 36  
11 5  
23 13  
2  
23 15  
15 23  

输出样例

2  
1  

题目来源

西北欧编程竞赛（Northwestern Europe）2003