eolymp
Competitions

9 Round Spiral. Round 1. Step 9.

n Div Tree

Given a tree having n nodes numbered from 1 to n, You have to find the number of paths (u, v) such that on path from u to v there should not exist any pair of nodes (a, b) such that a divides b.

Input

First line consists of a single integer denoting n. Following n1 lines consists of two space separated integers u, v denoting there is an edge between node numbered u and node numbered v.

Output

Print the required answer.

Time limit 2 seconds
Memory limit 122.17 MiB
Input example #1
2
1 2
Output example #1
0