题目 A：预订房间 (Booking)

题目描述

Bruceland 的女王想要举办 $Q$ 场不同的派对来庆祝她的就职典礼。每场派对都有 $N$ 个人参加。 为了让参加第 $i$ 场派对的每个人都感到开心，总人数与所用房间数的比值必须是一个介于 $a_i$ 和 $b_i$ 之间的整数。

也就是说，如果使用 $m_i$ 个房间来举办第 $i$ 场派对，必须满足：

且 $\frac{N}{m_i}$ 必须是整数。

作为女王选定的庆典大臣，你需要为每场派对确定满足条件的最少房间数 $m_i$。如果无法满足条件，则 $m_i = -1$。

输入格式

• 第一行包含两个整数：$N$ ($1 \le N \le 10^{14}$) 和 $Q$ ($1 \le Q \le 10^6$)。
• 接下来 $Q$ 行，每行包含两个空格分隔的整数 $a_i$ 和 $b_i$ ($1 \le a_i \le b_i \le N$)。

输出格式

• 输出 $Q$ 行，第 $i$ 行包含一个整数 $m_i$。如果不存在满足条件的 $m_i$，输出 $-1$。

样例

输入 1

20 3
3 6
4 20
6 9

输出 1

4
1
-1