说明

有 $n$ 个集合 $S_1\sim S_n$，初始全为空。

$q$ 次操作，每次操作给定正整数 $a,b$，表示令 $S_a\gets S_a\cup \{b\}$，然后求出如下问题的答案：

• 假设 $S_a$ 中每个数可以用无数次，选取若干个（至少 $1$ 个）$S_a$ 中的数相加，可以得到 $1\sim 50000$ 中的多少个正整数？

输入格式

第一行，两个正整数 $n,q$（$1\le n\le 100$，$1\le q\le 10^5$）。

接下来 $q$ 行，每行两个正整数 $a,b$（$1\le a\le n$，$1\le b\le 50000$），描述一次操作。

输出格式

输出 $q$ 行，每行一个正整数，表示答案。

1 2
1 3
1 5

16666
49996

2 4
2 35625
1 25139
1 37795
2 17791

1
1
2
3

提示

样例解释

样例一解释：

• 第一次操作后，可以得到 $3$ 的倍数，不大于 $50000$ 的有 $16666$ 个。
• 第二次操作后，不能得到的数只有 $1,2,4,7$。

子任务