Hôm nay trong giờ học, vì bản tính thích mày mò của mình, Miku đã tạo ra một xâu "siêu đối xứng". Đó là xâu có độ dài chẵn, mà khi ta chia đôi xâu gốc thành hai phần bằng nhau, ta vẫn thu được hai xâu đối xứng có cùng độ dài.

Ví dụ, xâu aaaa là một xâu "siêu đối xứng" vì khi chia đôi, ta thu được hai xâu là aa và aa đều là xâu đối xứng. Xâu aab hay aaa không phải là xâu "siêu đối xứng" vì không thỏa mãn định nghĩa của Miku.

Miku đố bạn một bài toán như sau:

Cho xâu ~S~, với ~|S| \le 10^6~. Các chữ cái trong xâu ~S~ đều là các ký tự tiếng Anh viết thường. Hỏi tồn tại bao nhiêu xâu "siêu đối xứng" theo định nghĩa của Miku là xâu con liên tiếp của xâu S?

INPUT

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \le N \le 10^6~) là độ dài của xâu ~S~.
• Dòng thứ hai chứa xâu ~S~ chỉ có ký tự từ ~a~ đến ~z~.

OUTPUT

• In ra dòng duy nhất là đáp số bài toán.

SAMPLE INPUT 1

5
ababa

SAMPLE OUTPUT 1

4

Giải thích: Các xâu "siêu đối xứng" thu được là ab, ba, ab, ba

SAMPLE INPUT 2

5
aaaaa

SAMPLE OUTPUT 2

6

Giải thích: Các xâu "siêu đối xứng" thu được là aa, aa, aa, aa, aaaa, aaaa.

SUBTASKS