Problem B. Badger ≡

Statement

A badger is hiding in its complicated burrow, which is a long straight tunnel. The borrow is separated into N consecutive chambers, numbered 1 through N. The badger is very smart and sleeps in one of the chambers each night.

A team of two hunters learned about badger's habits and came up with a shrewd plan. Each night they will check the chambers with a certain step. In particular, on night i they check all the chambers with numbers divisible by A_i or B_i.

The badger will be caught if at least one hunter will check a chamber that it is sleeping in.

Your task is to find the number of safe chambers for the night i, i.e. chambers that the badger can sleep in without any of the hunters finding it.

Input format

The first line of the input contains two integers N and K — the number of chambers in the borrow and the number of nights.

The following K lines each contain two integers A_i, B_i — step size of each of the hunters.

Output format

Output K integers — numbers of safe chambers in the badger's borrow for each of the nights.

Constraints

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

Sample tests

10 2
2 3
1 4

3
0

100 3
2 3
3 15
17 19

33
67
90