Cho hai số nguyên dương ~L~ và ~R~. Số tròn chục là số chia hết cho ~10~.

Yêu cầu:
Đếm xem có bao nhiêu số nguyên dương tròn chục lớn hơn ~L~ và nhỏ hơn ~R~.

Input

• Dòng đầu tiên chứa số nguyên dương ~L~;
• Dòng thứ hai chứa số nguyên dương ~R~.
  > ~(0 < L < R < 10^{18})~

Output

• In ra một số nguyên duy nhất là số lượng số thoả mãn yêu cầu đề bài.

Subtasks

• Subtask 1 (~60\%~ số điểm): ~R \leq 10^6~
• Subtask 2 (~20\%~ số điểm): ~R \leq 10^9~
• Subtask 3 (~20\%~ số điểm): Không có ràng buộc gì thêm.

Sample Test

Input

5
30

Output

2

Note
Có ~2~ số tròn chục nằm giữa ~5~ và ~30~ là: ~10~, ~20~.

Cho một robot được lập trình di chuyển trên một hàng ngang gồm các ô vuông. Mỗi ô được đặt tên bằng các kí tự theo thứ tự từ ~'𝐴'~ đến ~'𝑍'~ và được lặp lại vô hạn. Ban đầu robot xuất phát ở ô thứ ~1~ có tên là ~'𝐴'~ và nhảy đến các ô tiếp theo quy luật: lần ~1~ nhảy ~1~ ô, lần ~2~ nhảy ~2~ ô, lần ~3~ nhảy ~3~ ô, ~…~, lần ~𝑁~ nhảy ~𝑁~ ô. Vậy sau ~𝑁~ lần nhảy thì robot đang ở ô nào?

Dữ liệu:

Gồm một số nguyên dương ~N~ là số lần nhảy của robot ~(N \le 10^9)~.

Kết quả:

Một kí tự duy nhất là tên của ô sau ~N~ lần robot nhảy.

Ràng buộc

• Có ~60\%~ số test ứng với ~60\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 10^3;~
• ~20\%~ số test khác ứng với ~20\%~ số điểm của bài thoả mãn: ~𝑁 ≤ 10^6;~
• ~20\%~ số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.

Ví dụ

Input

1

Output

B

Giải thích: Sau ~1~ lần nhảy, robot ở ô thứ ~2~, có tên là kí tự ~B~.

Input

4

Output

K

Giải thích: Sau ~4~ lần nhảy, robot ở ô thứ ~11~, có tên là kí tự ~K~.

Input

7

Output

C

Giải thích: Sau ~7~ lần nhảy, robot ở ô thứ ~29~, có tên là kí tự ~C~.

Một dãy số được gọi là ~''~đẹp~''~ nếu mỗi phần tử trong dãy đó đều có số lần xuất hiện không vượt quá ~2~. Ví dụ:

• ~[1, 5, 2, 4, 3], [6, 9, 9, 6], [100]~ là các dãy đẹp.
• ~[3, 3, 3, 4, 4], [7, 7, 8, 7]~ và ~[100, 100, 100]~ không phải là các dãy đẹp.

Cho dãy ~a~ có ~n~ phần tử, hãy đếm số cặp chỉ số ~(l, r)~ sao cho ~a_l, a_{l+1}, ..., a_r~ là dãy đẹp.

Input

• Dòng đầu tiên chứa số nguyên dương ~n;~
• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n.~

Output

In ra kết quả là số cặp chỉ số ~(l, r)~ thoả mãn đề bài.

Scoring

• Subtask 1 [20%]: ~n \le 50; \ a_i \le 50;~
• Subtask 2 [15%]: ~n \le 500; \ a_i \le 500;~
• Subtask 3 [15%]: ~n \le 5000; \ a_i \le 5000;~
• Subtask 4 [50%]: ~n \le 5 \times 10^5; \ a_i \le 5 \times 10^5.~

Examples

Input

4
1 2 1 1

Output

9

Giải thích: Các cặp chỉ số ~(l, r)~ thoả mãn đề bài là: ~(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4).~

Input

6
4 5 4 5 4 5

Output

18

Cho một chuỗi kí tự gồm các kí tự chữ viết hoa, có bao nhiêu cách chọn ra bộ kí tự AMS khác nhau. Các kí tự được chọn phải để theo thứ tự trước sau như ban đầu.

Ví dụ, với câu CHAO AMS có ~2~ bộ kí tự AMS, tính theo vị trí là ~(3, 7, 8)~ và ~(6, 7, 8)~.

Input

Nhập vào một xâu văn bản ~S~ có tối đa ~10^6~ kí tự. Các kí tự đều là chữ in hoa.

Output

Ghi ra số cách chọn bộ kí tự AMS.

Ví dụ

Input

CHAO AMS

Output

2

Input

AMSER IN AMS

Output

4