e-olymp
Competitions

Dynamic programming on Trees - Top Level

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 second
Memory limit 122.17 MiB
Input example #1
2
1 2
Output example #1
0