Gene

A DNA sequence is a string made of the four characters a, c, g, and t. In this problem, a KOI gene is any string that can be formed by the following rules.

1. at and gc are KOI genes.
2. If a string X is a KOI gene, then aXt and gXc are also KOI genes.
3. If strings X and Y are KOI genes, then their concatenation XY is also a KOI gene.

A subsequence is obtained by deleting zero or more characters from the original sequence and keeping the remaining characters in order. Given a DNA sequence, find the maximum length of a subsequence that is a KOI gene. If no such subsequence exists, the length is 0.

The first line contains the DNA sequence to analyze. The length of the sequence is at most 500.

Print the length of the longest subsequence of the input DNA sequence that is a KOI gene. If there is no KOI gene, print 0.