Trong số học, số phong phú là số mà tổng các ước số dương của số đó (không kể chính nó) lớn hơn số đó.

Ví dụ: Số 18 có tổng các ước (không kể 18): ~1+2+3+6+9=21>18~ Số 10 có tổng các ước (không kể 10): ~1+2+5=8<10~

Khi đó ta nói số 18 là số phong phú còn số 10 không là số phong phú.

Yêu cầu: Cho một số tự nhiên ~N~, tìm số phong phú nhỏ nhất lớn hơn hoặc bằng ~N~.

Input

Gồm một số tự nhiên ~N~ (~0 < N < 10^8~).

Output

Ghi ra số phong phú nhỏ nhất lớn hơn hoặc bằng ~N~.

Sample Input 1

18

Sample Output 1

18

Sample Input 2

10

Sample Output 2

12

Subtasks

• Subtask 1 (50% số test): ~N \le 10^5~.
• Subtask 2 (50% số test): ~N < 10^8~.

Một hệ thống máy tính đang lưu trữ ~N~ tập tin, tập tin thứ ~i~ được đặt tên là ~S_i~. Nhận thấy rằng có nhiều tập tin không cần thiết, người ta cần xóa đi một số tập tin của hệ thống máy tính.

Cụ thể, người ta đã thực hiện ~Q~ thao tác xóa tập tin. Mỗi thao tác được biễu diễn bởi một kí tự ~c~, cho biết thao tác này xóa đi các tập tin có tên chứa ít nhất một kí tự ~c~. Sau mỗi thao tác xóa, hãy cho biết còn lại bao nhiêu tập tin trong hệ thống máy tính.

Input

• Dòng đầu tiên gồm hai số nguyên ~N~ và ~Q~ (~1 \le N, Q \le 10^5~).
• ~N~ dòng tiếp theo, dòng thứ ~i~ gồm xâu kí tự ~S_i~ độ dài không vượt quá 8, chỉ gồm các kí tự chữ cái in thường là tên của tập tin thứ ~i~.
• ~Q~ dòng tiếp theo, mỗi dòng gồm một kí tự chữ cái in thường ~c~ là mô tả một thao tác xóa.

Output

Gồm ~Q~ dòng, dòng thứ ~i~ gồm số tập tin còn lại trong hệ thống máy tính sau khi thực hiện thao tác xóa thứ ~i~.

Sample Input 1

5 3
chuc
cac
ban
thi
tot
a
b
c

Sample Output 1

3
3
2

Subtasks

• Subtask 1 (40% số test): ~N, Q \le 100~.
• Subtask 2 (60% số test): Không có ràng buộc gì thêm.

Cho lưới ô vuông hình chữ nhật ~m \times n~, mỗi ô chỉ chứa một giá trị 0 hoặc 1. Có bao nhiêu cách khác nhau để đi từ ô ~(1,1)~ đến ô ~(m, n)~.

Biết rằng mỗi lần đi chỉ được đi xuống dưới (từ ô ~(i, j)~ đến ô ~(i+1, j)~) hoặc sang phải (từ ô ~(i, j)~ đến ô ~(i, j+1)~) và không được đi vào ô có giá trị 1 (kể cả ô xuất phát ~(1,1)~).

Input

• Dòng đầu là 2 số nguyên dương ~m~ và ~n~ (~m, n \le 50~).
• ~m~ dòng tiếp theo, mỗi dòng gồm ~n~ số (0 hoặc 1) viết liền nhau của một hàng trong bảng.

Output

Ghi ra số đường đi khác nhau tìm được.

Sample Input 1

3 4
0001
0100
0000

Sample Output 1

3

Subtasks

• Subtask 1: Có 60% số test ~n, m \le 30~.
• Subtask 2: Có 40% số test ~n, m \le 50~.

Một số tự nhiên lớn hơn 10 được gọi là số siêu nguyên tố nếu cứ xóa bỏ chữ số hàng đơn vị của số đó ta luôn được số mới là số nguyên tố.

Ví dụ số 293 là số siêu nguyên tố vì 293, 29, 2 là các số nguyên tố. Số 17 không phải số siêu nguyên tố vì 1 không phải số nguyên tố.

Yêu cầu: Cho hai số nguyên dương ~a~ và ~b~ (~a \le b~). Đếm số lượng số siêu nguyên tố trong phạm vi từ ~a~ tới ~b~.

Input

Gồm hai số nguyên dương ~a~ và ~b~ (~a \le b \le 10^{12}~) cách nhau một khoảng trống.

Output

Ghi ra số lượng số siêu nguyên tố tìm được.

Sample Input 1

23 36

Sample Output 1

3

Trong ví dụ 1, các số siêu nguyên tố là 23, 29, 31.

Sample Input 2

100 311

Sample Output 2

4

Trong ví dụ 2, các số siêu nguyên tố là 233, 239, 293, 311.

Subtasks

• Có 15% test tương ứng 15% số điểm có ~a \le b \le 100~.
• Có 15% test tương ứng 15% số điểm có ~a \le b \le 10000~.
• Có 30% test khác tương ứng 30% số điểm có ~a \le b \le 10^6~.
• Có 40% test còn lại tương ứng 40% số điểm không có ràng buộc gì thêm.