在冰淇淋城里，开张了 $n$ 家冰淇淋摊。但在开张时，所有摊位都没有可售卖的冰淇淋球。

在接下来的 $q$ 天里，冰淇淋球的货运将会送达某些摊位。在 $q$ 天中的每一天，会给出两个整数 $a$ 和 $b$，表示摊位 $a$ 在当天收到了一批口味（数值）为 $b$ 的冰淇淋球。

在每个摊位，都可以制作冰淇淋组合。一个组合可以使用该摊位现有的冰淇淋球，其中每个冰淇淋球可以使用任意多次，且一个组合至少包含 $1$ 个冰淇淋球。

一个组合的价值等于该组合中所有冰淇淋球口味数值的总和，口味可以重复。我们只对价值小于或等于 $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

1 2
1 3
1 5

输出格式 1

16666
49996

输入格式 2

2 4
2 35625
1 25139
1 37795
2 17791

输出格式 2

1
1
2
3

说明

第一个样例解释：在第一天之后，第一个摊位可以制作的冰淇淋组合价值为所有小于或等于 $50000$ 的 $3$ 的倍数。共有 $16666$ 种这样的组合。在第二天之后，唯一无法制作的组合价值为：$1, 2, 4, 7$。所有其他组合价值均可制作，总计 $49996$ 种。