Джоске в подарок от дедушки получил огромный неориентированный взвешенный полный\(^\dagger\) граф \(G\), который содержит \(10^{18}\) вершин. Особенность подарка в том, что вес ребра между различными вершинами \(u\) и \(v\) равен \(\gcd(u, v)^\ddagger\). Джоске решил поэкспериментировать и сделать новый граф \(G'\). Для этого он выбирает два целых числа \(l \le r\), и оставляет только такие вершины \(v\), что \(l \le v \le r\), а также оставляет только ребра между оставшимися вершинами.
Теперь Джоске интересуется, сколько различных весов ребер в графе \(G'\). Так как граф получился огромный, он просит вашей помощи.
\(^\dagger\) Полным графом называется простой неориентированный граф, в котором каждая пара различных вершин смежна.
\(^\ddagger\) \(\gcd(x, y)\) обозначает наибольший общий делитель (НОД) чисел \(x\) и \(y\).
Выходные данные
Для каждого набора входных данных выведите единственное число — количество различных весов среди оставшихся ребер.
Примечание
Графа \(G'\) для первого набора входных данных. На рисунке видно, что в графе \(2\) различных веса ребер.
В пятом наборе входных данных остается лишь одна вершина, из которой не исходит ни одного ребра, поэтому ответ — \(0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
2 4
16 24
2 6
1 10
3 3
2562 2568
125 100090
|
2
6
3
5
0
5
50045
|