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 n − 1 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.