Tandem Repeats occur in DNA when a pattern of one or more nucleotides is repeated,and the repetitions are directly adjacent to each other. For example, consider the sequence:</p>

• ATTCGATTCGATTCG

This contains 9 Tandem Repeats:

• ATTCGATTCGATTCG
• ATTCGATTCGATTCG
• ATTCGATTCGATTCG
• ATTCGATTCGATTCG
• ATTCGATTCGATTCG
• ATTCGATTCGATTCG
• ATTCGATTCGATTCG
• ATTCGATTCGATTCG
• ATTCGATTCGATTCG

Given a nucleotide sequence, how many Tandem Repeats occur in it? 

입력 형식

There will be several test cases in the input. Each test case will consist of a single string on its own line, with from 1 to 100,000 capital letters, consisting only of A, G, T and C. This represents a nucleotide sequence. The input will end with a line with a single 0.

출력 형식

For each test case, output a single integer on its own line, indicating the number Tandem Repeats in the nucleotide sequence. Output no spaces, and do not separate answers with blank lines.

예제 입력

AGGA
AGAG
ATTCGATTCGATTCG
0

예제 출력

1
1
9