Đề bài

Cho một số chuỗi có độ dài không quá ~10^6~. Với mỗi chuỗi, hãy tìm số lần lặp lại tối đa của một tiền tố liên tiếp giống nhau.

Ví dụ:

• Với chuỗi "ababab", ta có thể thấy nó được tạo thành từ 3 lần lặp của "ab", nên đáp án là 3.
• Với chuỗi "aaaa", chuỗi này gồm 4 lần lặp của "a", nên đáp án là 4.
• Với chuỗi "abcd", không có mẫu con nào lặp lại liên tục, nên đáp án là 1.

Input

• Gồm nhiều dòng, mỗi dòng chứa một chuỗi.
• Kết thúc khi gặp một dòng chỉ chứa dấu ".".

Output

• Với mỗi chuỗi đầu vào, in ra một số nguyên duy nhất trên một dòng - số lần lặp tối đa của một tiền tố liên tiếp giống nhau.

Ví dụ

Input

abcd
aaaa
ababab
.

Output

1
4
3