유전자

DNA 서열은 네 문자 a, c, g, t로 이루어진 문자열이다. 이 문제에서 KOI 유전자는 다음 규칙으로 만들 수 있는 문자열이다.

1. at와 gc는 KOI 유전자이다.
2. 문자열 X가 KOI 유전자이면 aXt와 gXc도 KOI 유전자이다.
3. 문자열 X와 Y가 KOI 유전자이면 두 문자열을 이어 붙인 XY도 KOI 유전자이다.

부분 서열은 원래 서열에서 문자 0개 이상을 지우고 남은 문자를 순서대로 이어 얻는 문자열이다. 주어진 DNA 서열의 부분 서열 중 KOI 유전자인 것의 최대 길이를 구하여라. 그런 부분 서열이 없으면 길이는 0이다.

첫째 줄에 분석할 DNA 서열이 주어진다. DNA 서열의 길이는 최대 500이다.

입력 DNA 서열의 부분 서열 중 가장 긴 KOI 유전자의 길이를 첫째 줄에 출력한다. KOI 유전자가 없으면 0을 출력한다.