Задача B. Badger ≡

Условие

Барсук прячется в своей сложной норе, которая представляет собой длинный прямой тоннель. Нора разделена на N последовательных камер, пронумерованных от 1 до N. Барсук очень умный и каждую ночь он спит в одной из камер.

Команда из двух охотников узнала о привычках барсука и разработала хитрый план. Каждую ночь они будут проверять камеры с определённым шагом. А именно, в ночь i они проверяют все камеры, номера которых кратны числу A_i или B_i.

Барсук будет пойман, если хотя бы один охотник проверит камеру, в которой он спит.

Ваша задача — определить, сколько у барсука безопасных камер в ночь i, то есть камер, в которых он может спать, и ни один охотник его не найдёт.

Формат входных данных

Первая строка содержит два целых числа N и K — количество камер в норе и количество ночей.

Следующие K строк содержат по два целых чисел A_i, B_i — числа, определяющие шаг проверки для каждого охотника.

Формат выходных данных

Выведите K целых чисел — количество безопасных камер в норе барсука по дням.

Ограничения

1 ≤ N ≤ 10⁹, 1≤K≤10⁴ 1 ≤ A_i, B_i ≤ 10⁹

Примеры тестов

10 2
2 3
1 4

3
0

100 3
2 3
3 15
17 19

33
67
90