Chris Martin

Last night the mad scientist Changho kidnapped Jaehyun Koo and extracted his DNA. Human DNA has length $n$ and consists of four bases: A, C, G, and T.

Changho dislikes Jaehyun, who always teased him, and instead prefers the handsome Chris Martin of Coldplay. From this he formed a theory: the DNA that is least similar to Jaehyun's DNA is Chris Martin's DNA.

The similarity of two DNA strings is defined as the length of their longest common subsequence (LCS). A subsequence of a DNA string is any string obtained by deleting zero or more bases from it, and the longest common subsequence of two DNA strings is a longest string that is a subsequence of both.

You, too, are currently kidnapped by Changho. If you cannot find Chris Martin's DNA, who knows what will happen. Given Jaehyun's DNA, among all DNA strings of the same length $n$, find the minimum possible similarity to it. In other words, output the smallest LCS length that can occur between the given DNA and any DNA string $T$ of length $n$.

The first line contains the length $n$ of the human DNA. ($1 \le n \le 10000$)

The second line contains a DNA string of length $n$. Every character of the string is one of A, C, G, T.

On the first line, print the minimum possible similarity, i.e. the smallest longest-common-subsequence length between the given DNA and any DNA string of length $n$.