Trường THPT Chuyên tỉnh Lào Cai tổ chức giải bóng đá cấp trường chào mừng các bạn học sinh lớp 10; nhà trường dự kiến có ~n~ đội tham gia. Luật chơi như sau: Tại mỗi vòng, các đội sẽ tham gia bốc thăm chọn các cặp đá loại trực tiếp. Đội chiến thắng sẽ vào vòng sau. Nếu số đội tham gia là lẻ, thì sẽ có một đội bốc được lá thăm đặc biệt; đội đó có thể bị loại hoặc được vào vòng tiếp theo. Cứ như vậy cho tới khi tìm được đội vô địch. Tít là một thành viên trong ban tổ chức. Tít đã tính được số trận đấu nhưng chưa chắc chắn, nên hỏi các bạn trong lớp 10 chuyên Tin vừa được tuyển vào trường.

Yêu cầu: Các em hãy tính giúp bạn Tít xem số trận đấu của giải trong hai trường hợp là bao nhiêu.

Input

• Đọc dữ liệu từ tệp Caula.inp gồm một số nguyên dương duy nhất ~n~ (~n \le 10^8~) là số lượng đội tham gia.

Output

• Kết quả được ghi ra tệp Caula.out gồm 2 dòng:
• Dòng 1: Ghi ra tổng số trận đấu nếu đội bốc được lá thăm đặc biệt sẽ được vào thẳng vòng tiếp.
• Dòng 2: Ghi ra tổng số trận đấu nếu đội bốc phải lá thăm đặc biệt sẽ bị loại.

Ràng buộc

• Có 50% số điểm ứng với các test có ~n \le 10^4~.
• Có 50% số điểm ứng với các test có ~n \le 10^8~.

Sample Input 1

5

Sample Output 1

4
3

Bạn Bình thi đỗ vào lớp 10 trường THPT chuyên tỉnh Lào Cai. Để thưởng cho kết quả học tập của con, mẹ bạn Bình cho tiền đi chợ chơi. Bình rất thích mua áo để về khoe với các bạn. Ở chợ, có ~n~ cái áo được xếp thành hàng đánh số từ ~1~ tới ~n~. Những áo cùng loại thì có giá giống nhau và những áo khác loại thì có giá khác nhau. Bình định mua mỗi loại 1 áo nhưng Bình không biết là có bao nhiêu loại áo.

Yêu cầu: Em hãy giúp Bình đếm xem trong chợ có tổng cộng bao nhiêu loại áo khác nhau.

Input

• Đọc dữ liệu từ tệp Cau1b.inp gồm:
• Dòng đầu tiên chứa số tự nhiên ~n~ (~n \le 10^5~) là số áo có trong chợ.
• Dòng thứ hai chứa ~n~ số ~a_i~ (~0 \le a_i \le 10^5~) là giá của những cái áo có trong chợ.

Output

• Kết quả được ghi ra tệp Cau1b.out gồm một số nguyên duy nhất là số loại áo có trong chợ.

Ràng buộc

• Có 50% số điểm ứng với các test có ~n \le 10^3~.
• Có 50% số điểm ứng với các test có ~n \le 10^5~.

Sample Input 1

8
1 1 1 3 4 4 5 5

Sample Output 1

4

An là một học sinh của trường THPT chuyên. Trong thời gian rảnh, An rất thích đọc sách tại thư viện trường. An thấy trong thư viện mỗi quyển sách đều được gán một mã số. Mã số là một chuỗi các ký tự bao gồm các chữ cái và chữ số (có phân biệt chữ in hoa, in thường, không có khoảng trống). Hôm nay, An vào thư viện để mượn sách về đọc. Trong lúc mượn sách, An liền nảy ra ý nghĩ đếm xem mã số của cuốn sách đang cầm có bao nhiêu kí tự phân biệt, mỗi kí tự đó xuất hiện bao nhiêu lần.

Yêu cầu: Em hãy giúp bạn An chỉ ra số lượng các ký tự phân biệt và số lần xuất hiện của kí tự đó trong mã số của cuốn sách An đang cầm.

Input

• Đọc dữ liệu từ tệp Cau2a.inp gồm một dòng duy nhất là mã số của cuốn sách.

Output

• Kết quả được ghi ra tệp Cau2a.out gồm:
• Dòng 1: Ghi ra số lượng kí tự khác nhau đã được dùng để đặt mã số.
• Các dòng tiếp theo, mỗi dòng ghi ra các kí tự có xuất hiện trong mã số, kèm theo số lần xuất hiện lần lượt theo thứ tự trong bảng mã ASCII.

Ràng buộc

• Có 50% số điểm ứng với các test có số kí tự của xâu ~S \le 10^2~.
• Có 50% số điểm ứng với các test có số kí tự của xâu ~S \le 10^4~.

Sample Input 1

TamQuoc001

Sample Output 1

9
0 2
1 1
Q 1
T 1
a 1
c 1
m 1
o 1
u 1

Sau kỳ thi tuyển sinh vào lớp 10 THPT chuyên. Tít đã quyết định dành thời gian nghỉ hè để học về lập trình trang web. Với những mã nguồn mở hiện có trên web, việc học lập trình trở nên khá đơn giản. Hôm nay, Tít đã học đến nội dung về cơ sở dữ liệu và tạo tài khoản cho người dùng. Tít muốn viết một đoạn chương trình để kiểm tra xem mật khẩu người dùng đặt như vậy đã đảm bảo là mật khẩu mạnh hay chưa (Mật khẩu được gọi là mật khẩu mạnh nếu nó thỏa mãn các ràng buộc: gồm ít nhất ~8~ kí tự, gồm cả chữ số, chữ hoa, chữ thường và kí tự đặc biệt (kí tự được gọi là đặc biệt nếu nó khác chữ cái in hoa, in thường và chữ số)).

Yêu cầu: Em hãy giúp bạn Tít viết chương trình để kiểm tra xem mật khẩu người dùng đã đảm bảo yêu cầu chưa. In ra Yes nếu mật khẩu mạnh và in ra No nếu mật khẩu chưa đủ mạnh.

Input

• Đọc dữ liệu vào từ tệp Cau2b.inp gồm:
• Dòng đầu tiên là số lượng mật khẩu người dùng đã đặt cần kiểm tra ~T~ (~T \le 10^4~).
• ~T~ dòng tiếp theo, một dòng là một xâu kí tự ~S~, gồm một chuỗi các kí tự liên tục, không có khoảng trống (số kí tự của ~S \le 50~).

Output

• Kết quả được ghi ra tệp Cau2b.out gồm:
• In ra trên ~T~ dòng, mỗi dòng là một thông báo Yes nếu mật khẩu mạnh hoặc No nếu mật khẩu chưa đủ mạnh.

Ràng buộc

• Có 50% số điểm ứng với các test có ~T \le 10^2~.
• Có 50% số điểm ứng với các test có ~T \le 10^4~.

Sample Input 1

4
A123456a@
A123456A@
a123456a@
Aaaaaaaa@

Sample Output 1

Yes
No
No
No

Giải thích:

• A123456a@: Mật khẩu thỏa mãn điều kiện.
• A123456A@: Mật khẩu không có kí tự thường.
• a123456a@: Mật khẩu không có kí tự hoa.
• Aaaaaaaa@: Mật khẩu không có chữ số.

Trong lớp của Nam có ~n~ bạn học sinh. Hôm nay, thầy giáo yêu cầu các bạn điểm danh bằng cách đọc số thứ tự của mình trong lớp. Số thứ tự bạn nào được đọc lên nghĩa là bạn đó đã có mặt.

Trong tiết Tin học có ~m~ bạn học sinh đi học, mỗi bạn tới lượt mình tự nhớ và điểm danh số thứ tự ~a_i~ (~a_i \le n~). Không loại trừ trường hợp một bạn có thể điểm danh nhầm cho số thứ tự của bạn khác.

Yêu cầu: Em hãy chỉ ra số lượng những bạn vắng và số thứ tự nào đã vắng mặt trong sổ điểm danh của thầy giáo.

Input

• Lấy dữ liệu từ tệp Cau3.inp gồm:
• Dòng đầu tiên chứa hai số tự nhiên ~n~, ~m~ (~m \le n \le 10^5~).
• Dòng thứ hai chứa ~m~ số nguyên dương ~a_1, a_2, a_3, ..., a_m~.

Output

• Kết quả được ghi ra tệp Cau3.out gồm:
• Dòng đầu là số lượng các bạn vắng trong sổ điểm danh.
• Dòng thứ hai chứa các số nguyên tăng dần là số thứ tự các bạn vắng.

Ràng buộc

• Có 50% số điểm ứng với các test có ~n \le 10^5~.
• Có 50% số điểm ứng với các test có ~m \le 10^5~.

Sample Input 1

6 4
3 5 2 6

Sample Output 1

2
1 4

Hôm nay, bé Đạt đi học được cô giáo dạy về hình tam giác vuông. Nhà bé Đạt có ~t~ hộp diêm mỗi hộp có ~n~ que diêm với độ dài lần lượt là ~a_1, a_2, ..., a_n~. Vì mới học nên bé Đạt muốn xem có ~3~ que diêm nào có thể ghép thành hình tam giác vuông không. Em hãy giúp bé Đạt nhé!

Yêu cầu: Em hãy giúp bé Đạt kiểm tra xem độ dài của các que diêm có thể ghép thành hình tam giác vuông hay không.

Input

• Lấy dữ liệu từ tệp Cau4.inp gồm:
• Dòng đầu chứa số nguyên ~t~ (~t \le 50~) là số lượng hộp diêm của nhà bé Đạt.
• Các dòng tiếp theo tương ứng với số hộp diêm là:
• Một dòng là số lượng que diêm ~n~ trong từng hộp (~0 < n \le 700~).
• Dòng tiếp theo chứa các số nguyên ~a_1, a_2, ..., a_n~ (~a_i \le 10^9~) là độ dài của ~n~ que diêm trong từng hộp.

Output

• Kết quả được ghi ra tệp Cau4.out gồm:
• Ghi ra ~t~ dòng tương ứng với hộp diêm thứ ~t~. Ghi ra YES nếu hộp diêm đó có cách xếp thành hình tam giác vuông, ghi ra NO nếu không có.

Ràng buộc

• Có 50% số test với ~n \le 100~ ứng với 50% số điểm của bài.
• Có 50% số test với ~n \le 700~ ứng với 50% số điểm của bài.

Sample Input 1

2
5
1 2 4 3 5
5
1 1 24 16 13

Sample Output 1

YES
NO

Giải thích:

• Ở hộp diêm thứ nhất: Có ~3~ que diêm có độ dài ~3, 4, 5~ có thể xếp thành ~1~ tam giác vuông nên in ra YES.
• Ở hộp diêm thứ hai: Không có bộ ~3~ que diêm nào có độ dài có thể xếp thành ~1~ tam giác vuông nên in ra NO.

Mỗi số đều mang một ý nghĩa vô cùng đặc biệt. Theo quan niệm của nhiều người, số ~5~ là một số đặc biệt trong các số đặc biệt; số ~5~ tương ứng là số sinh, đại diện cho sự chính trực, một số đại cát, đại lợi. Vì đam mê với các con số nên Tít đã tìm hiểu rất nhiều cổ tích về số ~5~. Hôm nay, trong tiết Tin học của lớp 10 chuyên Tin, thầy giáo đưa ra yêu cầu đếm các số nguyên tố trong đoạn từ ~L~ đến ~R~. Tít thấy nhiệm vụ này khá quen thuộc nên quyết định thử thách mình với yêu cầu đếm xem trong đoạn ~L~ đến ~R~ có bao nhiêu số là số nguyên tố và đồng thời có tổng các chữ số chia hết cho ~5~. Tít gọi các số đặc biệt này là các số siêu nguyên tố.

Yêu cầu: Em hãy giúp bạn Tít đếm xem trong đoạn từ ~L~ đến ~R~ có bao nhiêu số là số siêu nguyên tố.

Input

• Đọc dữ liệu từ tệp Cau5.inp gồm:

• Dòng đầu tiên chứa số nguyên dương ~T~ là số lượng Test trong file (~T \le 3.10^5~).

• ~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~L~, ~R~ (~L \le R \le 3.10^6~) theo thứ tự, phân tách nhau bởi dấu cách.

Output

• Kết quả được ghi ra tệp Cau5.out gồm:

• Ghi ra ~T~ dòng, mỗi dòng ghi một số là số lượng số siêu nguyên tố có trong đoạn ~[L, R]~, tương ứng theo thứ tự dữ liệu Test đầu vào.

Ràng buộc

• 20% số test có ~1 \le T \le 100~; ~L, R \le 200~.

• 20% số test tiếp theo có ~1 \le T \le 10^3~; ~L, R \le 2.10^3~.

• 30% số test tiếp theo có ~1 \le T \le 10^4~; ~L, R \le 2.10^5~.

• 30% số test cuối cùng có ~1 \le T \le 3.10^5~; ~L, R \le 3.10^6~.

Sample Input 1

3
1 10
4 20
6 15

Sample Output 1

1
2
0

Giải thích:

• Trong đoạn ~[1, 10]~ có ~1~ số siêu nguyên tố là ~5~.

• Trong đoạn ~[4, 20]~ có ~2~ số siêu nguyên tố là ~5~ và ~19~ (~1 + 9 = 10~).

• Trong đoạn ~[6, 15]~ không có số siêu nguyên tố nào.