Số nguyên dương ~N~ gọi là số phản nguyên tố nếu bản thân ~N~ và các số tạo thành từ việc xóa đi những chữ số bên phải của ~N~ đều không phải là số nguyên tố.

Ví dụ:

• Số 9426 là số phản nguyên tố vì 9426; 942; 94; 9 đều không phải là số nguyên tố.
• Số 3752 không phải là số phản nguyên tố vì 3752; 375 không phải là số nguyên tố nhưng 37 và 3 là số nguyên tố

Yêu cầu: Kiểm tra các số nguyên dương ~a, b, c~ có phải là số phản nguyên tố hay không?

INPUT

• Nhập vào từ bàn phím một dòng duy nhất ghi ba số nguyên ~a, b, c~ (~1 \le a, b, c \le 10^9~), mỗi số cách nhau một khoảng trắng.

OUTPUT

• In ra 3 dòng có cấu trúc như sau:
  • Dòng 1: ghi ~1~ nếu ~a~ là số phản nguyên tố, ghi ~0~ nếu ~a~ không phải là số phản nguyên tố.
  • Dòng 2: ghi ~1~ nếu ~b~ là số phản nguyên tố, ghi ~0~ nếu ~b~ không phải là số phản nguyên tố.
  • Dòng 3: ghi ~1~ nếu ~c~ là số phản nguyên tố, ghi ~0~ nếu ~c~ không phải là số phản nguyên tố.

SAMPLE INPUT 1

33 292 46

SAMPLE OUPUT 1

0
0 
1

SAMPLE INPUT 2

174 68 290

SAMPLE OUPUT 2

0
1
0

SUBTASKS

• ~40 \%~ test với ~1 \le a, b, c < 100~
• ~40 \%~ test với ~10^7 < a, b, c \le 10^9~
• ~20 \%~ test với ~10^3 < a, b, c < 10^6~

Cho một dãy các kí tự. Dãy kí tự số liên tiếp của dãy đã cho là dãy chỉ có các kí tự số liên tiếp với nhau.

Ví dụ, trong dãy ~aooo1db274fg~ có 7 dãy kí tự số liên tiếp là ~1; 2; 7; 4; 27; 74; 274~

Yêu cầu: Cho một dãy kí tự chỉ gồm các chữ cái và chữ số. Tìm độ dài dãy kí tự số liên tiếp dài nhất của dãy đã cho.

INPUT

• Nhập vào từ bàn phím một dãy kí tự (độ dài dãy không quá ~10^6~ kí tự).

OUTPUT

• In ra một số nguyên là độ dài dãy kí tự số liên tiếp dài nhất của dãy đã cho

SAMPLE INPUT 1

aooo23db200fg

SAMPLE OUPUT 1

3

SAMPLE INPUT 2

ab1cdgf

SAMPLE OUPUT 2

1

SAMPLE INPUT 3

sdfghj

SAMPLE OUPUT 3

0

SUBTASKS

• ~50 \%~ test có độ dài nhỏ hơn ~255~
• ~50 \%~ test có độ dài từ ~10^3~ đến ~10^6~

Cho dãy ~A~ gồm ~N~ số nguyên dương. Mỗi cặp số trong dãy ~A~ được gọi là cặp số khác nhau nếu cặp số này ở vị trí khác nhau trong dãy số và có giá trị khác nhau.

Yêu cầu: Đếm xem trong dãy ~A~ có bao nhiêu cặp số khác nhau.

INPUT

• Dòng 1: Ghi số nguyên dương ~N~ (~3 \le N \le 10^6~)
• Dòng 2: Ghi ~N~ số nguyên của dãy ~A~, mỗi số có giá trị không quá ~10^6~ và cách nhau ít nhất 1 khoảng trắng.

OUTPUT

• Ghi số lượng các cặp số khác nhau

SAMPLE INPUT

4
4 5 6 4

SAMPLE OUPUT

5

SUBTASKS

• ~40 \%~ test có ~3 \le N \le 5000~
• ~40 \%~ test có ~10^4 < N \le 10^5~
• ~20 \%~ test có ~5 \times 10^5 < N \le 10^6~

Nhân dịp mở cửa trở lại phố đi bộ Ninh Bình sau dịch Covid-19, ban tổ chức đã trang trí phố đi bộ bằng 1 dây đèn nháy có ~n~ bóng đèn được đánh số từ ~1~ đến ~n~. Các đèn nháy được lập trình điều khiển lần lượt thay đổi trạng thái theo quy tắc sau:

• Lần 1: Thay đổi trạng thái các bóng đèn có số thứ tự chia hết cho 1
• Lần 2: Thay đổi trạng thái các bóng đèn có số thứ tự chia hết cho 2
• Lần 3: Thay đổi trạng thái các bóng đèn có số thứ tự chia hết cho 3
• ...
• Lần ~n~: Thay đổi trạng thái các bóng đèn có số thứ tự chia hết cho ~n~

Biết rằng ban đầu tất cả các bóng đèn đều tắt. Khi thay đổi trạng thái, các bóng đèn chuyển từ bật sang tắt hoặc tắt sang bật.

Yêu cầu: Hãy cho biết sau ~n~ lần thay đổi trạng thái thì từ bóng đèn ~p~ sang bóng đèn ~q~ có bao nhiêu bóng đèn đang bật?

INPUT

• Nhập vào ba số nguyên ~p, q, n~ (~1 \le p < q \le n \le 10^{18}~)

OUTPUT

• Ghi số lượng bóng đèn bật

SAMPLE INPUT 1

3 6 8

SAMPLE OUPUT 1

1

SAMPLE INPUT 2

2 11 12

SAMPLE OUPUT 2

2

SUBTASKS

• ~40 \%~ test có ~n \le 3000~
• ~40 \%~ test có ~10^4 \le n \le 10^5~
• ~20 \%~ test có ~10^7 < n \le 10^{18}~