设 $A$ 和 $B$ 为两棵无向树。我们定义和 $A + B$ 为通过在 $A$ 中的任意节点与 $B$ 中的任意节点之间连接一条边所能得到的所有无向树的集合。

类似地，我们定义标量 $k$ 与树 $A$ 的积为 $k$ 个 $A$ 的副本通过 $k-1$ 条新边连接而成的树的集合。例如，$1 \cdot A$ 是仅包含树 $A$ 本身的集合。集合 $2 \cdot A$ 即为 $A + A$。同理，$3 \cdot A$ 是由 3 个 $A$ 的副本通过 2 条额外的边连接成一棵树的所有树的集合，以此类推。

我们称树 $A$ 整除树 $B$，如果存在正整数 $k$，使得 $B$ 包含在集合 $k \cdot A$ 中。我们观察到，类似于自然数中的整除性，任何树都能被其自身以及“单位”树（仅由单个节点组成的树）整除。

给定一棵树 $T$，任务是计算有多少棵不同的树整除它。

我们称两棵树是不同的，如果其中一棵树的顶点无法通过重新标记得到另一棵树。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示树的顶点数。 接下来的 $n-1$ 行，每行包含两个不同的整数 $u$ 和 $v$ ($1 \le u, v \le n$)，表示树中一条边的两个端点。

输出格式

输出一个整数，表示整除 $T$ 的不同树的数量。

样例

样例输入 1

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

样例输出 1

3