题目描述

有一棵包含 $n$ 个结点的树，每个点都有权值（$1$ 或 $2$）。

请找出满足每个点周围所有的点的点权的最大公约数或者最小公倍数等于自身点权的方案个数，对 $10007$ 取模。

输入格式

第一行一个正整数 $T$，表示数据组数。

接下来对于每组测试数据，第一行输入一个正整数 $n$，表示树的结点个数。

接下来 $n-1$ 行每行输入两个正整数 $u,v(1 \le u,v \le n)$，表示树上的一条边。

输出格式

对于每组测试数据输出一行一个整数，表示答案对 $100007$ 取模后的值。

样例输入输出

1
7
1 2
2 3
2 4
4 5
5 6
5 7

6

提示

$6$ 种情况分别是：

$1112222$

$1111222$

$1111111$

$2221111$

$2222111$

$2222222$

对于 $100\%$ 的数据，$1 \le T \le 10,2 \le n \le 10^5,\sum{n}≤10^6$。