Số nguyên tố là số tự nhiên lớn hơn ~1~ và có hai ước là một và chính nó. Một số nguyên tố được gọi là số nguyên tố "đẹp" khi nó không chứa chữ số ~3, 5~ và ~7~.

Ví dụ: Các số ~2, 11, 19~ là các số nguyên tố "đẹp", các số ~3, 5, 7, 37, 73~ không phải là số nguyên tố "đẹp".

Cho số nguyên dương ~N (1 \leq N \leq 10^{6})~.

Yêu cầu: Đếm tất cả các số nguyên tố "đẹp" thuộc đoạn từ ~1~ đến ~N~.

Dữ liệu:

• Gồm một số nguyên dương ~N~.

Kết quả:

• Ghi ra một số nguyên dương duy nhất là số lượng số nguyên tố "đẹp".

Ví dụ:

Sample Input

20

Sample Output

3

Giải thích:

Với ~N = 20~, thì có các số nguyên tố là ~2, 3, 5, 7, 11, 13, 17, 19~. Như vậy, chỉ có ~3~ số nguyên tố ~2, 11, 19~ thỏa mãn yêu cầu bài toán.

Xét trò chơi xếp hình chữ nhật với các que diêm như sau: Có ~n~ que diêm, que thứ ~i~ có độ dài ~d_i~. Người chơi cần chọn ra 4 que diêm để có thể xếp thành một hình chữ nhật, giả sử ~4~ que diêm mà người chơi chọn có độ dài lần lượt là ~a, b, c, d(a \leq b \leq c \leq d)~, khi đó có thể xếp được thành một hình chữ nhật nếu ~a=b~ và ~c=d~. Người chơi xếp được hình chữ nhật có diện tích càng lớn sẽ càng được điểm cao.

Yêu cầu: Cho ~d_1, d_2, \ldots, d_n~ là độ dài của ~n~ que diêm. Hãy tìm cách chọn ~4~ que diêm để xếp được thành một hình chữ nhật có diện tích lớn nhất.

Dữ liệu:

• Dòng đầu tiên ghi số nguyên dương ~K~ là số lượng bộ dữ liệu. Tiếp đến là ~K~ nhóm dòng, mỗi nhóm tương ứng với một bộ dữ liệu có cấu trúc như sau:
  • Dòng thứ nhất ghi một số nguyên dương ~n~;
  • Dòng tiếp theo chứa ~n~ số nguyên dương ~d_1, d_2, \ldots, d_n\left(d_i \leq 10^9\right)~.

Kết quả:

• Ghi ra gồm ~K~ dòng, mỗi dòng ghi một số nguyên là diện tích của hình chữ nhật xếp được tương ứng với bộ dữ liệu trong file dữ liệu vào (ghi -1 nếu không tồn tại cách chọn nào xếp được hình chữ nhật).

Ví dụ:

Sample Input

2
5
5 3 1 5 1
4
1 2 3 4

Sample Output

5
-1

Ràng buộc:

• Có ~40\%~ số test, ứng với ~40\%~ số điểm của bài có ~n \leq 30~;
• Có ~40\%~ số test, ứng với ~40\%~ số điểm của bài có ~n \leq 3000~;
• Có ~20\%~ số test còn lại, ứng với ~20\%~ số điểm của bài có ~n \leq 300000~.

Một xâu được gọi là mật khẩu "an toàn" nếu xâu đó thỏa mãn:

• Có độ dài ít nhất bằng ~6~.
• Chứa ít nhất một chữ cái in hoa ('A'…'Z').
• Chứa ít nhất một chữ cái in thường ('a'…'z').
• Chứa ít nhất một chữ số ('0'…'9').

Ví dụ: "a1B2C3","tinHoc6" là hai mật khẩu "an toàn", còn "a1B2C", "a1b2c3", "A1B2C3", "tinHoc" đều không là mật khẩu "an toàn".

Một lần, Minh nhìn thấy một xâu ~S~ có độ dài ~n (n \le 10^6 )~ chỉ gồm các loại kí tự: chữ cái in hoa, chữ cái in thường và chữ số. Minh muốn đếm xem có bao nhiêu cặp chỉ số ~(i, j)~ thỏa mãn hai điều kiện:

• ~1 \le i \lt j \le n.~
• Xâu con gồm các ký tự liên tiếp từ ~i~ đến ~j~ là mật khẩu "an toàn".

Yêu cầu: Bạn hãy giúp Minh tính số lượng cặp ~(i, j)~ thỏa mãn điều kiện nêu trên.

Dữ liệu vào:

• Gồm một dòng duy nhất chứa duy nhất xâu ~S~.

Kết quả:

• Ghi ra một số nguyên không âm là kết quả tìm được.

Ví dụ:

Sample Input

abc3456789PQ

Sample Output

6

Giải thích:

Trong ví dụ trên có ~6~ mật khẩu "an toàn" là: "c3456789P", "c3456789PQ", "bc3456789P", "bc3456789PQ", "abc3456789P", "abc3456789PQ".

Ràng buộc:

• Có ~40\%~ số điểm ứng với các test có ~n \le 10^2~.
• Có ~30\%~ số điểm ứng với các test có ~n \le 10^3~.
• Có ~30\%~ số điểm ứng với các test còn lại có ~n \le 10^6~.