Сегодня Маленький Джон потратил все свои сбережения, чтобы купить отрезок. Теперь он хочет построить на нём дом. Отрезок положительных целых чисел \([l,r]\) называется взаимно простым, если числа \(l\) и \(r\) взаимно простые\(^{\text{∗}}\).
Взаимно простой отрезок \([l,r]\) называется минимальным взаимно простым, если он не содержит\(^{\text{†}}\) никаких взаимно простых отрезков, не равных самому себе. Ниже в разделе примечаний приведены примеры минимальных и не минимальных взаимно простых отрезков.
Дан отрезок \([l,r]\) положительных целых чисел, найдите количество минимальных взаимно простых отрезков, содержащихся в \([l,r]\).
Выходные данные
Для каждого набора входных данных выведите количество минимальных взаимно простых отрезков, содержащихся в \([l,r]\), в отдельной строке.
Примечание
В первом наборе входных данных дан отрезок \([1,2]\). Отрезки, содержащиеся в \([1,2]\), следующие:
- \([1,1]\): Этот отрезок является взаимно простым, так как числа \(1\) и \(1\) являются взаимно простыми, и не содержит никаких других отрезков внутри. Таким образом, \([1,1]\) является минимальным взаимно простым.
- \([1,2]\): Этот отрезок является взаимно простым. Однако, поскольку он содержит \([1,1]\), который также является взаимно простым, \([1,2]\) не является минимальным взаимно простым.
- \([2,2]\): Этот отрезок не является взаимно простым, потому что числа \(2\) и \(2\) имеют \(2\) общих положительных делителя: \(1\) и \(2\).
Таким образом, отрезок \([1,2]\) содержит \(1\) минимальный взаимно простой отрезок.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 2
1 10
49 49
69 420
1 1
9982 44353
|
1
9
0
351
1
34371
|