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 **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.

Input example #1

2 1 2

Output example #1

0