题目背景

“天尽头，何处……”

在花果山，猴在“猴王杯”败给鳖山皇帝胖虎后决定强身健体。为了完成“夜空校园”晨跑打卡，他听着洛天依的歌在操场狂奔了 3 km。结果因用力过猛，猴突发胸口剧痛、呼吸困难——他竟然把肺跑破，气胸了！

还在花店为自己的月亮挑选玫瑰花的大聪明听到这消息吓坏了，赶紧拨打 $120$，将猴抬上了救护车送往医院。

在救护车上，伴随着警笛声和耳机里的洛天依歌声，缺氧的猴脑海中浮现出奇妙的幻觉。由于长期的心理阴影，脑海中骋哥在群里发出的一条条“素质低下”的举报记录，错综复杂地串联成了一棵“举报之树”；而耳机里洛天依跳跃的音符，则交织成了另一棵散发柔和光芒的“治愈音符树”。

题目描述

猴脑海中的幻觉可以抽象为两棵大小均为 $N$ 的无根树 $T_1$（代表举报之树）和 $T_2$（代表治愈音符树），两棵树的节点集合均为 $V = \{1, 2, \dots, N\}$。 猴需要用意念找出一个节点集合 $S \subseteq V$，使得该集合同时满足以下两个条件： 清晰的辩护线：在树 $T_1$ 中，由节点集合 $S$ 导出的子图恰好是一条简单路径，这意味着猴理出了一条不走回头路的时间线来为自己辩护。 治愈的音律链：在树 $T_2$ 中，由节点集合 $S$ 导出的子图恰好也是一条简单路径，代表着音律的完美连结与内心伤痛的治愈。 请你帮躺在担架上的猴算一算，他脑海中最多能选出多少个节点，即求出满足上述条件的最大节点集合大小 $K = |S|$。

由于大聪明忙着帮猴找塑料袋了，猴就把问题抛给了你。

输入格式

输入包含多组测试数据。

第一行包含一个正整数 $T$，表示测试数据组数。

对于每组测试数据：

• 第一行包含一个正整数 $N$（$1 \le N \le 10^5$），表示树的大小。
• 接下来 $N-1$ 行，每行包含两个整数 $u,v$（$1 \le u,v \le N$），表示树 $T_1$ 中存在一条连接 $u,v$ 的无向边。
• 接下来 $N-1$ 行，每行包含两个整数 $x,y$（$1 \le x,y \le N$），表示树 $T_2$ 中存在一条连接 $x,y$ 的无向边。

保证输入给出的 $T_1,T_2$ 均为合法的树。

另外，保证所有测试数据满足 $\sum N \le 10^5$。

输出格式

对于每组测试数据，输出一行一个整数，表示满足条件的最大 $K$。

样例

输入

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

输出

4
3

样例解释

对于第一组数据，可以选择 $S=\{1,2,3,4\}$。在 $T_1$ 中，$S$ 导出的子图为路径 $1-2-3-4$；在 $T_2$ 中，$S$ 导出的子图也为路径 $1-2-3-4$，因此答案至少为 $4$。如果选择全部 $5$ 个点，则在 $T_1$ 中点 $3$ 的度数为 $3$，导出的子图不是一条简单路径，所以答案为 $4$。

对于第二组数据，可以选择 $S=\{1,2,3\}$。在 $T_1$ 中，$S$ 导出的子图为路径 $2-1-3$；在 $T_2$ 中，$S$ 导出的子图为路径 $1-2-3$。由于 $T_1$ 是以 $1$ 为中心的星形树，任意由点集导出的简单路径最多只能包含中心点和两个叶子，因此答案为 $3$。