All Tracks Algorithms Graphs Graph Representation Problem

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 Format:
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 Format:
Print the required answer.

Constraints:
\(1 \le N \le 10^5\)
\(1 \le u, v \le N\)