Given a tree with \(N\) nodes numbered \(1\) to \(N\) and \(N - 1\) edges, rooted at node \(1\). Find the number of unordered pair of distinct vertices \((i,j)\) such that there exists exactly one prime number on the simple path between vertex \(i\) and \(j\).

Note:

We only need to consider unordered pairs i.e. \((i,j) \) and \((j,i) \) are counted once.
The values of nodes in the path will be the node numbers.

Input format

The first line contains \(N\) denoting the number of vertices in the tree.
The next \(N - 1\) lines contain two space-separated integers \(u\), \(v\) denoting an edge between vertex \(u \) and \(v\).

Output format

Print a single integer, denoting the number of such pairs \((i,j)\).

Constraints

\(1 \le N \le 10^5 \\ 1 \le u, v \le N\)