{"raw_statement":[{"iden":"problem statement","content":"We have a string $S$ of length $N$ consisting of `A`, `T`, `C`, and `G`.\nStrings $T_1$ and $T_2$ of the same length are said to be complementary when, for every $i$ ($1 \\leq i \\leq l$), the $i$\\-th character of $T_1$ and the $i$\\-th character of $T_2$ are complementary. Here, `A` and `T` are complementary to each other, and so are `C` and `G`.\nFind the number of non-empty contiguous substrings $T$ of $S$ that satisfies the following condition:\n\n*   There exists a string that is a permutation of $T$ and is complementary to $T$.\n\nHere, we distinguish strings that originate from different positions in $S$, even if the contents are the same."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 5000$\n*   $S$ consists of `A`, `T`, `C`, and `G`."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $S$"},{"iden":"sample input 1","content":"4 AGCT"},{"iden":"sample output 1","content":"2\n\nThe following two substrings satisfy the condition:\n\n*   `GC` (the $2$\\-nd through $3$\\-rd characters) is complementary to `CG`, which is a permutation of `GC`.\n*   `AGCT` (the $1$\\-st through $4$\\-th characters) is complementary to `TCGA`, which is a permutation of `AGCT`."},{"iden":"sample input 2","content":"4 ATAT"},{"iden":"sample output 2","content":"4\n\nThe following four substrings satisfy the condition:\n\n*   `AT` (the $1$\\-st through $2$\\-nd characters) is complementary to `TA`, which is a permutation of `AT`.\n*   `TA` (the $2$\\-st through $3$\\-rd characters) is complementary to `AT`, which is a permutation of `TA`.\n*   `AT` (the $3$\\-rd through $4$\\-th characters) is complementary to `TA`, which is a permutation of `AT`.\n*   `ATAT` (the $1$\\-st through $4$\\-th characters) is complementary to `TATA`, which is a permutation of `ATAT`."},{"iden":"sample input 3","content":"10 AAATACCGCG"},{"iden":"sample output 3","content":"6"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}