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 \)