Задано дерево из n вершин, пронумерованных от 1 до n. Найдите количество таких путей (u, v), что на пути от u к v не существует таких пар вершин (a, b) что a делит b.

Входные данные

Первая строка содержит число n. Каждая из следующих n − 1 строк содержит два целых числа u, v указывающих на существование ребра межу вершинами u и v.

Выходные данные

Выведите требуемый ответ.