Trong thành phố kem, có ~n~ quầy kem vừa mở cửa. Tuy nhiên, ở thời điểm khai trương thì chưa quầy nào có viên kem nào để bán.

Trong ~q~ ngày tiếp theo, các lô kem sẽ lần lượt được giao tới một số quầy. Ở ngày thứ ~i~, ta biết hai số nguyên ~a~ và ~b~, nghĩa là quầy ~a~ nhận được một lô kem có vị ~b~.

Tại mỗi quầy, người ta có thể tạo ra các tổ hợp kem. Một tổ hợp chỉ sử dụng các viên kem hiện có ở quầy đó; mỗi viên kem có thể dùng lại bao nhiêu lần cũng được; và một tổ hợp phải gồm ít nhất ~1~ viên kem.

Giá trị của một tổ hợp bằng tổng các vị của những viên kem tạo nên tổ hợp đó, và các vị có thể lặp lại. Ta chỉ quan tâm tới những tổ hợp có giá trị không vượt quá ~50000~, vì các tổ hợp lớn hơn thì quá ngọt.

Sau mỗi ngày, hãy in ra có bao nhiêu giá trị khác nhau của tổ hợp kem có thể tạo được tại quầy vừa nhận thêm kem trong ngày hôm đó.

Input

Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~q~.

Mỗi trong ~q~ dòng tiếp theo chứa hai số ~a~ và ~b~, mô tả quầy nhận thêm kem và hương vị của lô kem được giao trong ngày đó.

Output

In ra ~q~ dòng, dòng thứ ~i~ là đáp án tương ứng sau ngày thứ ~i~.

Ràng buộc

• ~1 \le n \le 100~
• ~1 \le q \le 10^5~
• ~1 \le a \le n~
• ~1 \le b \le 50000~

Chấm điểm

• Subtask 1 (16 điểm): ~n = 1~, ~q \le 20~
• Subtask 2 (33 điểm): ~q \le 100~
• Subtask 5 (61 điểm): Không có ràng buộc bổ sung.

Sample Input 1

1 2
1 3
1 5

Sample Output 1

16666
49996

Sample Input 2

2 4
2 35625
1 25139
1 37795
2 17791

Sample Output 2

1
1
2
3

Giải thích

• Ví dụ 1: Sau ngày đầu tiên, các giá trị có thể tạo được ở quầy ~1~ là mọi bội số của ~3~ không vượt quá ~50000~, nên có ~16666~ giá trị. Sau ngày thứ hai, chỉ còn các giá trị ~1~, ~2~, ~4~, ~7~ là không tạo được; vì thế có tổng cộng ~49996~ giá trị hợp lệ.