Trong một kho hàng, mỗi vật phẩm được gắn một mã định danh là một số nguyên dương. Một robot có nhiệm vụ quét mã số này để phân loại vật phẩm theo quy tắc sau: Nếu mã định danh là số nguyên tố thì vật phẩm được đưa vào khay A, ngược lại, vật phẩm được đưa vào khay B.

Biết rằng: Số nguyên tố là số chỉ có đúng hai ước nguyên dương là ~1~ và chính nó. Ví dụ: ~2, 3, 5, 7, 11, \ldots~ là các số nguyên tố.

Yêu cầu

Cho ~3~ số nguyên ~a, b, c~ là mã định danh của ~3~ vật phẩm cần phân loại. Hãy xác định khay chứa mỗi vật phẩm theo quy tắc trên.

Input

Từ tệp văn bản CAU1.INP:

• Dòng ~1~ ghi số nguyên ~a~ ~\left(1 \le a \le 10^{12}\right)~ là mã định danh của vật phẩm ~1~;
• Dòng ~2~ ghi số nguyên ~b~ ~\left(1 \le b \le 10^{12}\right)~ là mã định danh của vật phẩm ~2~;
• Dòng ~3~ ghi số nguyên ~c~ ~\left(1 \le c \le 10^{12}\right)~ là mã định danh của vật phẩm ~3~.

Output

Ghi vào tệp văn bản CAU1.OUT gồm ~3~ dòng: Dòng thứ ~i~ ~\left(i = 1, 2, 3\right)~ ghi A nếu vật phẩm ~i~ được đưa vào khay A, ngược lại ghi B.

Ràng buộc

• Subtask 1 (80% số điểm): ~1 \le a, b, c \le 10^6~;
• Subtask 2 (20% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input

29
5
2026

Output

A
A
B

Giải thích

~29~ và ~5~ là số nguyên tố ~\rightarrow~ khay A.

~2026~ không phải là số nguyên tố ~\rightarrow~ khay B.

Trà sữa CocoD đang chạy chương trình khuyến mãi như sau: trên nắp mỗi ly trà sữa có in một mã số may mắn là số nguyên dương, nếu mã số này chia hết cho ~2026~ thì khách hàng sẽ được miễn phí ly trà sữa đó.

Bo đã mua ~n~ ly trà sữa ở CocoD, các ly được đánh số từ ~1~ đến ~n~. Ly thứ ~i~ ~\left(1 \le i \le n\right)~ có mã số may mắn là ~a_i~.

Yêu cầu

Cho ~n~ và dãy ~a_1, a_2, \ldots, a_n~. Hãy đếm số ly trà sữa Bo được miễn phí khi áp dụng chương trình khuyến mãi trên.

Input

Từ tệp văn bản CAU2.INP:

• Dòng ~1~ ghi số nguyên ~n~ ~\left(1 \le n \le 10^6\right)~;
• Dòng ~2~ ghi ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~\left(1 \le a_i \le 10^{18};\ 1 \le i \le n\right)~.

Output

Ghi vào tệp văn bản CAU2.OUT một số nguyên là số ly trà sữa Bo được miễn phí.

Ràng buộc

• Subtask 1 (80% số điểm): ~1 \le a_i \le 10^6;\ 1 \le i \le n~;
• Subtask 2 (20% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input

5
6078 29 4052 2905 5

Output

2

Giải thích

~6078~ và ~4052~ chia hết cho ~2026~ ~\rightarrow~ hai ly có mã này được miễn phí.

Vào cao điểm nắng nóng, để phòng tránh tai nạn đuối nước, nhà trường tổ chức cuộc thi Rung chuông vàng với chủ đề "Phòng chống đuối nước" cho học sinh toàn trường. Cuộc thi có thể lệ như sau:

Điểm số ban đầu của mỗi học sinh là ~0~. Với mỗi câu trả lời đúng cộng ~5~ điểm, câu trả lời sai trừ ~3~ điểm.

Có ~n~ học sinh tham gia cuộc thi, các học sinh được đánh số từ ~1~ đến ~n~. Học sinh thứ ~i~ ~\left(1 \le i \le n\right)~ có số câu trả lời đúng và số câu trả lời sai lần lượt là ~a_i, b_i~.

Yêu cầu

Cho ~n~, dãy ~a_1, a_2, \ldots, a_n~ và dãy ~b_1, b_2, \ldots, b_n~. Hãy tính điểm cao nhất và thấp nhất của cuộc thi.

Input

Từ tệp văn bản CAU3.INP:

• Dòng ~1~ ghi số nguyên ~n~ ~\left(2 \le n \le 10^6\right)~;
• Dòng ~2~ ghi ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ ~\left(0 \le a_i \le 50;\ 1 \le i \le n\right)~;
• Dòng ~3~ ghi ~n~ số nguyên ~b_1, b_2, \ldots, b_n~ ~\left(0 \le b_i \le 50;\ 1 \le i \le n\right)~.

Output

Ghi vào tệp văn bản CAU3.OUT:

• Dòng ~1~ ghi một số nguyên là điểm cao nhất của cuộc thi;
• Dòng ~2~ ghi một số nguyên là điểm thấp nhất của cuộc thi.

Ràng buộc

• Subtask 1 (40% số điểm): ~n = 2~;
• Subtask 2 (10% số điểm): Tất cả học sinh bằng điểm nhau;
• Subtask 3 (50% số điểm): Không có ràng buộc gì thêm.

Ví dụ 1

Input

3
9 12 10
1 4 3

Output

48
41

Ví dụ 2

Input

5
11 2 14 5 8
15 0 20 5 10

Output

10
10

Trước thềm World Cup 2026, để tăng doanh số bán hàng, một hãng bánh quy triển khai chương trình khuyến mãi "Gom thẻ rinh quà" với thể lệ như sau: Trong mỗi hộp bánh có một thẻ chứa mã dự thưởng; hai thẻ có mã dự thưởng giống nhau sẽ đổi được một phần quà lưu niệm và mỗi thẻ dự thưởng chỉ được sử dụng một lần.

Mã dự thưởng là một chuỗi có độ dài không quá ~15~ ký tự, gồm: các ký tự chữ cái in hoa trong bảng chữ cái tiếng Anh ~(A-Z)~ hoặc các ký tự chữ số ~(0-9)~ hoặc cả ký tự chữ cái và chữ số.

Ngay khi biết được chương trình khuyến mãi, Bo đã mua ~n~ hộp bánh, các hộp bánh được đánh số từ ~1~ đến ~n~. Hộp bánh thứ ~i~ ~\left(1 \le i \le n\right)~ có mã dự thưởng ~s_i~.

Yêu cầu

Cho ~n~ và dãy ~s_1, s_2, \ldots, s_n~. Hãy đếm số quà nhiều nhất mà Bo có thể đổi được từ chương trình khuyến mãi trên.

Input

Từ tệp văn bản CAU4.INP:

• Dòng ~1~ ghi số nguyên ~n~ ~\left(1 \le n \le 10^5\right)~;
• ~n~ dòng tiếp theo, dòng thứ ~i~ ~\left(1 \le i \le n\right)~ ghi mã dự thưởng ~s_i~.

Output

Ghi vào tệp văn bản CAU4.OUT một số nguyên là số quà nhiều nhất mà Bo có thể đổi được.

Ràng buộc

• Subtask 1 (10% số điểm): Tất cả các mã dự thưởng giống nhau;
• Subtask 2 (10% số điểm): ~n \le 10^3~;
• Subtask 3 (10% số điểm): Mã dự thưởng có độ dài không quá ~6~ kí tự, gồm: các kí tự chữ số ~(0-9)~ và không bắt đầu bằng kí tự ~0~;
• Subtask 4 (70% số điểm): Không có ràng buộc gì thêm.

Ví dụ 1

Input

5
WORLD2026
D2026
WORLD2026
WORLD2026
D2026

Output

2

Ví dụ 2

Input

5
29
05
2026
29
TS10

Output

1

Trong buổi tuyên truyền về an toàn trên không gian mạng, nhà trường giới thiệu một hệ thống nhận diện các số điện thoại có dấu hiệu quảng cáo hoặc lừa đảo. Để bảo vệ quyền riêng tư cá nhân, hệ thống này chỉ lưu trữ ~4~ chữ số cuối của mỗi số điện thoại, gọi là mã đuôi. Một mã đuôi (gồm đúng ~4~ chữ số) được gọi là mã nghi vấn nếu nó thỏa mãn đồng thời ~3~ điều kiện sau:

~1/~ Chữ số đầu tiên là ~2~ hoặc ~0~;

~2/~ Chữ số cuối cùng là ~2~ hoặc ~6~;

~3/~ Hai chữ số ở giữa giống nhau.

Ví dụ: ~2556, 0006, 2112~ là các mã nghi vấn; còn ~2229, 9129~ không là mã nghi vấn.

Hệ thống thu thập ~n~ số điện thoại, các số điện thoại được đánh số từ ~1~ đến ~n~. Số điện thoại thứ ~i~ ~\left(1 \le i \le n\right)~ có mã đuôi là ~s_i~. Hệ thống ghi nhận ~q~ truy vấn, mỗi truy vấn gồm hai số nguyên ~L, R~.

Yêu cầu

Cho ~n, s_1, s_2, \ldots, s_n~ và ~q~. Ứng với mỗi truy vấn, hãy đếm số lượng mã nghi vấn trong dãy ~s_L, s_{L+1}, \ldots, s_R~.

Input

Từ tệp văn bản CAU5.INP:

• Dòng ~1~ ghi hai số nguyên ~n~ và ~q~ ~\left(1 \le n \le 10^5;\ 1 \le q \le 5 \times 10^3\right)~;
• Dòng ~2~ ghi ~n~ mã đuôi ~s_1, s_2, \ldots, s_n~;
• ~q~ dòng tiếp theo, mỗi dòng ghi hai số nguyên ~L, R~ ~\left(1 \le L \le R \le n\right)~, biểu diễn một truy vấn.

Output

Ghi vào tệp văn bản CAU5.OUT gồm ~q~ dòng:

• Dòng thứ ~i~ ~\left(1 \le i \le q\right)~ ghi một số nguyên là số lượng mã nghi vấn ứng với truy vấn ~i~.

Ràng buộc

• Subtask 1 (10% số điểm): ~q = 1~;
• Subtask 2 (10% số điểm): ~n \le 10^3;\ q \le 10^3~;
• Subtask 3 (80% số điểm): Không có ràng buộc gì thêm.

Ví dụ

Input

8 4
2556 2229 0006 2112 9129 2002 0116 1236
1 4
2 8
5 7
4 8

Output

3
4
2
3

Giải thích

Các mã nghi vấn trong danh sách đã cho là: ~2556, 0006, 2112, 2002, 0116~;

• Truy vấn ~1~, xét các phần tử từ ~1~ đến ~4~, có ~3~ mã nghi vấn là ~2556, 0006, 2112~;
• Truy vấn ~2~, xét các phần tử từ ~2~ đến ~8~, có ~4~ mã nghi vấn là ~0006, 2112, 2002, 0116~;
• Truy vấn ~3~, xét các phần tử từ ~5~ đến ~7~, có ~2~ mã nghi vấn là ~2002, 0116~;
• Truy vấn ~4~, xét các phần tử từ ~4~ đến ~8~, có ~3~ mã nghi vấn là ~2112, 2002, 0116~.