Có N đoàn vận động viên về thăm sân vân động mới khánh thành của tỉnh Thái Nguyên, các đoàn được đánh số thứ tự từ 1 đến N, đoàn thứ i có ai vận động viên. Ban tổ chức quyết định thuê xe taxi 7 chỗ ngồi (kể cả tài xế) để chở các vận động viên vào sân vận động. Biết rằng vận động viên các đoàn chỉ ngồi xe riêng, nghĩa là không thể ghép vận động viên đoàn này ngồi cùng xe với các vận động viên của đoàn khác.

Yêu cầu: Cho chiếc xe taxi cần thuê để chở được tất cả vận động viên.

Dữ liệu: đọc từ bàn phím (thiết bị chuẩn)

Dòng 1: chứa một số nguyên dương N (N ≤ 10^2)

Dòng 2: chứa N số nguyên dương a1, a2, …., aN, lần lượt là số vận động viên của N đoàn. Các số không quá 10^3

Kết quả: ghi ra màn hình (thiết bị chuẩn), một số duy nhất số taxi cần thuê.

Ví dụ:

Input:

3
6 13 1

Output:

5

Giải thích:

Đoàn 1, có 6 VĐV cần 1 chiếc taxi

Đoàn 2, có 13 người cần 3 chiếc taxi

Đoàn 3, có 1 người cần 1 chiếc taxi

Tổng số cần 5 chiếc taxi.

Ràng buộc:

• 50% số điểm có N ≤ 10.

• 50% số điểm không có ràng buộc gì thêm.

Xâu đối xứng là xâu mà khi đọc từ trái sáng phải hay từ phải sang trái đều giống nhau. Xâu con của một xâu là một đoạn kí tự liên tiếp khác rỗng của xâu đó.

Yêu cầu: Cho xâu kí tự S. Hãy tìm xâu con đối xứng dài nhất của xâu S.

Dữ liệu: đọc từ bàn phím (thiết bị vào chuẩn), một dòng duy nhất chứa xâu S (không quá 104 kí tự)

Kết quả: ghi ra màn hình (thiết bị ra chuẩn), một số duy nhất là độ dài của xâu con đối xứng dài nhất.

Ví dụ:

Input:

ABCBA

Output:

5

Ràng buộc:

• 50% số điểm có độ dài của xâu S không quá 100.

• 50% số điểm không có ràng buộc gì thêm.

Số đẹp là số nguyên dương có số lượng ước nguyên tố phân biệt là số một nguyên tố. Cho dãy số gồm N số nguyên a1, a2, …, aN. Yêu cầu: Cho M câu hỏi, mỗi câu hỏi chứa 2 số nguyên dương L, R (L ≤ R), cho biết số lượng số đẹp trong đoạn từ vị trí L đến vị trí R trong dãy a.

Dữ liệu: đọc từ bàn phím (thiết bị vào chuẩn), gồm các dòng sau:

• Dòng 1: chứa hai số nguyên N, M (0 < N ≤ 10^5, 0 < M ≤ 10^3)

• Dòng 2: chứa N số nguyên dương a1, a2, …, aN. Các số trên cùng dòng cách nhau một dấu cách (|ai| ≤ 10^5)

• M dòng tiếp theo mỗi dòng chứa 2 số nguyên L và R (L ≤ R ≤ N)

Kết quả: ghi ra màn hình (thiết bị ra chuẩn), gồm M dòng, là câu trả lời tương ứng của M câu hỏi trong dữ liệu.

Ví dụ:

Input:

6 3
1 10 2 6 30 14
1 6
2 3
2 5

Output:

4
1
3

Giải thích:

Số 10 có 2 ước nguyên tố (2, 5) -> là số đẹp

Số 2 có 1 ước nguyên tố (2) -> không là số đẹp

Số 30 có 3 ước nguyên tố (2, 3, 5) -> là số đẹp

Ràng buộc:

• 20% số test thỏa M = 1; N ≤ 10^3

• 40% số test thỏa M ≤ 100; N ≤ 10^3

• 40% số test không có ràng buộc gì thêm.