Товарищ Дюжиков занимается подбором артистов для дня рождения Тимофея и заодно принимает поздравления с Таймыра.
Итак, товарища Дюжикова раз в n минут вызывает с Таймыра Илюша-альпинист, то есть в минуты n, 2n, 3n и так далее. Раз в m минут приходят артисты и выступают, то есть в минуты m, 2m, 3m и так далее. Поскольку связь работает плохо, ни одного звонка пропустить нельзя, зато вот артистов очень много. Если день длится z минут (то есть состоит из минут 1, 2, ..., z), сколько артистов надо утопить, чтобы во время звонков не было артистов? Считайте, что и звонок, и выступление артиста длятся ровно одну минуту.
Выходные данные
Выведите единственное число — минимальное количество артистов, которых надо утопить, чтобы во время звонков не было артистов.
Примечание
В первом тесте артисты приходят ежеминутно, так же звонит и Илья, поэтому всех артистов надо утопить.
Во втором тесте артисты со звонком пересекаются на 2-ой и 4-ой минутах.
В третьем тесте они пересекаются только на 6-ой минуте.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1 10
|
10
|
|
2
|
1 2 5
|
2
|
|
3
|
2 3 9
|
1
|