考虑两个无向图 $G_1$ 和 $G_2$。$G_1$ 和 $G_2$ 中的每个节点都有一个标签。当且仅当满足以下条件时，Doremy 称 $G_1$ 和 $G_2$ 是相似的：

• $G_1$ 中的标签两两不同，且 $G_2$ 中的标签两两不同。
• $G_1$ 中的标签集合 $S$ 与 $G_2$ 中的标签集合相同。
• 对于 $S$ 中的任意一对不同标签 $u$ 和 $v$，它们对应的节点在 $G_1$ 中属于同一个连通分量，当且仅当它们在 $G_2$ 中也属于同一个连通分量。

现在 Doremy 给你两棵有 $n$ 个节点的树 $T_1$ 和 $T_2$，节点编号为 $1$ 到 $n$。你可以进行以下操作任意次：

• 从 $T_1$ 中选择一个边集 $E_1$，从 $T_2$ 中选择一个边集 $E_2$，使得 $\overline{E_1}$ 和 $\overline{E_2}$ 相似。这里 $\overline{E}$ 表示仅保留树 $T$ 中的边集 $E$ 所得到的图（即边导出的子图）。换句话说，$\overline{E}$ 是通过从 $T$ 中删除所有不属于 $E$ 的边，并进一步删除所有孤立点而得到的。
• 将 $T_1$ 中的边集 $E_1$ 与 $T_2$ 中的边集 $E_2$ 进行交换。

现在 Doremy 想知道，在进行任意次操作后，可以得到多少种不同的 $T_1$？你能帮她求出答案吗？输出答案对 $10^9 + 7$ 取模的结果。

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 2 \cdot 10^4$) — 测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 10^5$) — 树 $T_1$ 和 $T_2$ 的节点数。

接下来的 $n - 1$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n$)，表示 $T_1$ 中的一条无向边。保证这些边构成一棵树。

接下来的 $n - 1$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n$)，表示 $T_2$ 中的一条无向边。保证这些边构成一棵树。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行一个整数，表示在进行任意次操作后，可以得到的不同 $T_1$ 的数量对 $10^9 + 7$ 取模的结果。

样例

输入样例 1

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

输出样例 1

1
2
4

说明

在第一个测试用例中，最多只有一种不同的 $T_1$，其唯一的边为 $(1, 2)$。

在第二个测试用例中，你可以选择 $T_1$ 中的边集 $\{(1, 3), (2, 3)\}$ 和 $T_2$ 中的边集 $\{(1, 2), (2, 3)\}$ 并交换它们。因此 $T_1$ 可以是 $1 - 3 - 2$ 或 $1 - 2 - 3$。

在第三个测试用例中，共有 $4$ 种不同的 $T_1$，如下图所示。