Xâu Pali đơn thuần là xâu đối xứng có các ký tự trong xâu hoàn toàn giống nhau. Cho xâu ~S~ có độ dài không quá 1000 kí tự chỉ gồm các chữ cái tiếng Anh viết thường.

Yêu cầu

Hãy tìm xâu Pali đơn thuần dài nhất trong xâu S.

Input

Nhập vào từ bàn phím một dòng chứa xâu S

Output

Xuất ra màn hình Một dòng duy nhất là yêu cầu của bài toán

Scoring

Ví dụ

Input

abcbbbsdcdd

Output

3

Cho một số nguyên dương ~N~ ~(N \le 5 * 10^5)~. Tìm số siêu bội nhỏ hơn hoặc bằng ~N~. Biết số siêu bội là số có tổng số mũ ở dạng thừa số nguyên tố là lớn nhất.

Ví dụ: ~12~ ~=~ ~2^2~ ~*~ ~3~ có tổng số mũ là ~2 + 1 = 3~

Yêu cầu

Tìm số siêu bội nhỏ hơn hoặc bằng ~N~ (Nếu có nhiều số như vậy thì in ra số lớn nhất).

Input

• Một dòng duy nhất là số nguyên dương ~N~ ~(N \le 5 * 10^5)~

Output

• Một dòng là yêu cầu của bài toán

Scoring

Ví dụ

Input

12

Output

12

Cho 2 số nguyên dương ~a~ và ~b~ ~(a \le b)~. Gọi ~G~ ~=~ ~BCNN(a, a+1, a+2, ..., b)~.

Yêu cầu

Tìm số chữ số 0 tận cùng của G.

Input

• Một dòng duy nhất là hai số nguyên dương ~a~ và ~b~ ~(a \le b \le 10^{18})~,

Output

• Một dòng duy nhất là yêu cầu của bài toán

Scoring

• Subtask ~1~ (~30\%~ số điểm): ~b\le 200~.
• Subtask ~2~ (~30\%~ số điểm): ~(b-a) \le 10^6~.
• Subtask ~3~ (~30\%~ số điểm): ~a = 1~
• Subtask ~4~ (~10\%~ số điểm): không có ràng buộc gì thêm

Ví dụ

Input

1 6

Output

1

Input

10 11

Output

1

Giải thích ví dụ

• Ví dụ 1: G = BCNN(1, 2, 3, 4, 5, 6) = 60, có một chữ số 0 tận cùng

Cho dãy ~A~ ~=~ ~(a_1, a_2, a_3, …, a_N)~ các số nguyên không âm. Vị trí ~(1 \le i \le N)~ được gọi là một vị trí tốt nếu như ~a_i~ bằng tổng của ~ba~ giá trị xuất hiện ở các vị trí nhỏ hơn ~i~ (mỗi giá trị có thể tham gia vào việc tính tổng nhiều lần).

Yêu cầu

Hãy đếm xem trong dãy A có bao nhiêu vị trí tốt?

Input

Cho trong file văn bản GPOS.INP có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 5000)~,
• Dòng thứ hai chứa ~N~ số nguyên không âm ~a_1, a_2, a_3, …, a_N~.~(0 \le a_i \le 10^5)~.

Output

Ghi ra file văn bản GPOS.OUT theo cấu trúc như sau:

• Một dòng duy nhất là yêu cầu của bài toán

Scoring

• Subtask ~1~ (~40\%~ số điểm): ~N\le 50~.
• Subtask ~2~ (~30\%~ số điểm): ~N\le 500~.
• Subtask ~3~ (~30\%~ số điểm): ~N\le 5000~

Ví dụ

Input

2
1 3

Output

1

Input

6
1 2 3 5 7 10

Output

4

Giải thích ví dụ

• Ví dụ 1: vị trí ~2~ là vị trí tốt vì ~a_2~ ~=~ ~a_1~ + ~a_1~ + ~a_1~ (mỗi giá trị có thể tham gia vào việc tính tổng nhiều lần)