BaoBao 是一个懒惰的男孩。他有 $n$ 对不同颜色的袜子，每个月洗一次。在洗衣机里，这些袜子会混在一起。

由于需要配对的袜子太多，BaoBao 将整个袜子配对过程分为两个阶段。

在第一阶段，BaoBao 随机将袜子两两配对。然后在第二阶段，BaoBao 重复以下操作，直到所有袜子都配对成功：BaoBao 选择若干对袜子，将它们放入他的魔法洗涤盆中，并使用他的魔法。如果魔法洗涤盆中的袜子在使用魔法时可以完美配对，魔法洗涤盆就会自动为 BaoBao 完成配对。然而，如果不能配对（这意味着盆中至少有一只袜子的颜色是唯一的），魔法盆就会爆炸，BaoBao 必须避免这种情况发生。

BaoBao 的魔法是有限的，在第一阶段之后，他需要知道他成功配对所有袜子所需的魔法洗涤盆的最小容量。洗涤盆的容量是指 BaoBao 一次可以放入魔法洗涤盆中的最大袜子对数。

输入格式

输入包含多个测试用例。第一行包含一个正整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示袜子对数。

接下来的 $n$ 行中，第 $i$ 行 ($1 \le i \le n$) 包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i, b_i \le 2^{30}$)，表示第一阶段后第 $i$ 对袜子中两只袜子的颜色。保证对于每一只袜子，都有且仅有一只颜色相同的袜子。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示魔法洗涤盆的最小容量。

样例

输入 1

1
5
1 2
2 3
1 3
4 5
4 5

输出 1

3

说明

在样例中，BaoBao 可以先将这三对袜子：$\{1,2\}, \{2,3\}, \{1,3\}$ 放入魔法洗涤盆中，它们会被配对成 $\{1,1\}, \{2,2\}, \{3,3\}$。然后，他可以将 $\{4,5\}, \{4,5\}$ 放入魔法洗涤盆中，它们会被配对成 $\{4,4\}, \{5,5\}$。因此，容量为 3 时可以成功配对所有袜子。通过暴力枚举可以证明，容量为 2 时是不可能完成的。