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:
Input format
Output format
Print a single integer, denoting the number of such pairs (i,j).
Constraints
1≤N≤1051≤u,v≤N
There are 7 such possible paths: