Số nguyên tố là số tự nhiên lớn hơn ~1~, chỉ có hai ước là ~1~ và chính nó. Cho số tự nhiên ~N~. Hãy sử dụng các chữ số của ~N~ để tạo ra các số nguyên tố.

Yêu cầu

Xác định số lượng số nguyên tố có thể tạo thành.

Dữ liệu đầu vào

Gồm một số tự nhiên ~N~ ~(N \le 10^7)~.

Dữ liệu đầu ra

Gồm một số nguyên là số lượng số nguyên tố tìm được.

Ví dụ

Ví dụ 1

INPUT

17

OUTPUT

3

Giải thích: Có ~3~ số nguyên tố được tạo thành từ các chữ số của ~17~ là: ~7, 17, 71~.

Mật khẩu an toàn là mật khẩu có độ dài ~n~, trong đó có ít nhất ~a~ ký tự hoa, ít nhất ~b~ ký tự thường, ít nhất ~c~ ký tự số và không có ~2~ ký tự liên tiếp giống nhau.

Biết quy tắc so sánh hai xâu ~X, Y~ theo thứ tự từ điển như sau:

• Hai xâu bằng nhau nếu giống nhau hoàn toàn.
• Xâu ~X~ lớn hơn xâu ~Y~ nếu ký tự đầu tiên khác nhau giữa chúng kể từ trái sang trong xâu ~X~ có mã ASCII lớn hơn.
• Nếu ~X~ và ~Y~ là ~2~ xâu có độ dài khác nhau và xâu ~X~ là đoạn đầu của xâu ~Y~ thì xâu ~X~ nhỏ hơn xâu ~Y~.

Yêu cầu

Với ~4~ số ~n, a, b, c~ cho trước, hãy đưa ra mật khẩu an toàn nhỏ nhất và lớn nhất theo thứ tự từ điển.

Dữ liệu đầu vào

Gồm một dòng chứa ~4~ số nguyên ~n, a, b~ và ~c~ ~(a + b + c \le n, 1 \le n \le 100)~.

Dữ liệu đầu ra

Gồm hai dòng:

• Dòng đầu tiên ghi mật khẩu có thứ tự từ điển nhỏ nhất.
• Dòng thứ hai ghi mật khẩu có thứ tự từ điển lớn nhất.

Ví dụ

Ví dụ 1

INPUT

8 2 5 1

OUTPUT

0ABababa
zyzyzZY9

Sử dụng từ "ít nhất" trong đề bài dễ gây nhầm lẫn với ví dụ đưa ra phía trên. Cần lưu ý xét cả trường hợp ~n > a + b + c~, nếu thực sự là "ít nhất" thì ở chuỗi lớn nhất phải sử dụng càng nhiều kí tự thường càng tốt, chẳng hạn zyzyzyZY9 có thứ tự từ điển lớn nhất khi ~n = 9~, trong khi đó tôi vẫn đang sử dụng "ít nhất" ~5~ kí tự thường (cụ thể là ~6~).

Trò chơi xếp hình bằng khối gỗ là một trò chơi phổ biến giúp kích thích trí tưởng tượng sáng tạo, rèn luyện tính kiên nhẫn và khả năng tư duy logic. Luật của trò chơi như sau: Có ~N~ khối gỗ với chiều rộng là ~1~ đơn vị, được đánh số từ ~1~ đến ~N~, chiều dài khối gỗ thứ ~i~ là ~a_i~ đơn vị. Nhiệm vụ của người chơi là chọn các khối gỗ phù hợp và dựng đứng các khối gỗ đó sát lại với nhau (chiều rộng tiếp xúc mặt sát theo phương ngang) sao cho nhận được một hình vuông với diện tích lớn nhất.

Yêu cầu

Xác định kích thước hình vuông có diện tích lớn nhất theo cách ghép của trò chơi.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 1000)~.
• Dòng thứ hai gồm ~N~ số nguyên ~a_1, a_2, \ldots, a_N~ là độ dài các khối gỗ ~(1 \le a_i \le N)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là kích thước hình vuông tìm được.

Ví dụ

Ví dụ 1

INPUT

5
5 4 1 4 3

OUTPUT

3

Giải thích: Có thể ghép ~3~ khối gỗ có chiều dài ~4, 3, 5~ hoặc ~4, 4, 3~ đều được hình vuông kích thước ~3 \times 3~ có diện tích lớn nhất.

Cho dãy ~N~ số nguyên dương ~a_1, a_2, \ldots, a_N~ và số nguyên dương ~k~. Thực hiện phép biến đổi dãy số bằng cách thao tác ~k~ lần chọn một chữ số tùy ý của một số bất kì trong dãy và thay chữ số đó bằng chữ số mới sao cho tổng các số nhận được càng lớn càng tốt.

Yêu cầu

Hãy xác định độ chênh lệch giữa tổng các số nhận được với tổng các số cho ban đầu là lớn nhất có thể.

Dữ liệu đầu vào

Gồm hai dòng:

• Dòng đầu tiên chứa hai số nguyên dương ~n~ và ~k~ ~(1 \le n \le 1000, 1 \le k \le 10^4)~.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1, a_2, \ldots, a_n~ ~(1 \le a_i \le 10^4, i = 1, 2, \ldots, n)~.

Dữ liệu đầu ra

Gồm một số nguyên duy nhất là độ chênh lệch tối đa có thể đạt được.

Ví dụ

Ví dụ 1

INPUT

3 1
99 5 85

OUTPUT

10

Giải thích:

• Tổng dãy ban đầu là ~99 + 5 + 85 = 189~;
• Chọn số ~85~ thực hiện ~1~ lần đổi chữ số ~8~ thành chữ số ~9~ được số ~95~;
• Tổng sau là ~99 + 5 + 95 = 199~;

Vậy độ chênh lệch là ~10~.