You are given a tree with n nodes. The nodes are numbered from 1 to n. Let us define the gcd of a path as the greatest common divisor of all values of the nodes in the path. Let $F(g)$ denote the number of simple paths on the tree whose gcd is g. Formally, $F(g)$ equals the number of sequences $p_1,p_2, \cdots , p_k$, such that $p_i$ and $p_{i+1}$ are connected by an edge for all $i < k$, and $p_i \neq p_j$ for $i \neq j$, and $gcd(p_1,p_2,\cdots p_k) = g$.

Find the values of $F(g)$ for all $1 \leq g \leq n$

Input
The first line contains n, the number of nodes in the tree.
Each of the next $n-1$ lines contain 2 integers $u,v$, denoting node u, and node v are connected by an edge.

Output
Print a single line containing n integers. The $i^{\text{th}}$ integer equals $F(i)$.

Constraints
$1 \le n \le 10^6$