Description

给一棵n个点的有标号无根树，你需要找到满足条件的路径u−v的条数。

我们称路径u-v满足条件当且仅当u,v且路径u-v上不存在点对(a,b),a,b满足gcd(a,b)=a。

注意：路径u−v和v−u是同一条路径。

Format

Input

第一行一个整数n,n<=10^5 接下来n−1行，每行两个用空格隔开的整数a,b，表示边(a,b) 只有路径 2 − 3 和 3 − 4 满足条件

Output

一行一个整数，代表要求的答案。

Samples

4 
3 1
3 2
3 4

2