Xâu ~20230322~ có thể sắp xếp lại thành ~02320232~, tức là xâu ~0232~ viết liền hai lần. Một xâu chỉ gồm các chữ số được gọi là may mắn nếu nó có thể sắp xếp lại thành (hoặc vốn đã là) một xâu nào đó viết liền hai lần.

Cho xâu ~S~ chỉ gồm các chữ số. Hãy đếm số cặp chỉ số ~(l, r)~ thỏa mãn đồng thời:

• ~1 \le l \le r \le |S|~, trong đó ~|S|~ là độ dài của ~S~;
• xâu con liên tiếp gồm các ký tự từ vị trí ~l~ đến vị trí ~r~ của ~S~ là xâu may mắn.

Dữ liệu vào

Một dòng duy nhất chứa xâu ~S~. Xâu ~S~ có thể bắt đầu bằng chữ số ~0~.

Kết quả

In ra một số nguyên duy nhất là số cặp tìm được.

Ví dụ

Đầu vào:

20230322

Đầu ra:

4

Giải thích: Bốn cặp thỏa mãn là ~(1, 6), (1, 8), (2, 7)~ và ~(7, 8)~.

Đầu vào:

0112223333444445555556666666777777778888888889999999999

Đầu ra:

185

Đầu vào:

3141592653589793238462643383279502884197169399375105820974944

Đầu ra:

9

Giới hạn

• ~1 \le |S| \le 5 \cdot 10^5~
• ~S~ chỉ gồm các chữ số từ ~0~ đến ~9~.