시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 18 2 2 40.000%

문제

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:

  • 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.

예제 입력 1

AGGA
AGAG
ATTCGATTCGATTCG
0

예제 출력 1

1
1
9

힌트