#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/problems/faang/07

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/problems/faang/07

Repovive

Complement Pair Count - FAANG Problems | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

MAANG07. Complement Pair Count

100 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

Given $n$ DNA sequences (strings over the alphabet $\{A, C, G, T\}$ ), count the number of complementary pairs.

Two DNA sequences are complementary if they have the same length and at every position, the characters are complements: $A \leftrightarrow T$ and $C \leftrightarrow G$ .

For example, $\texttt{ACGT}$ and $\texttt{TGCA}$ are complementary. $\texttt{AAA}$ and $\texttt{TTT}$ are complementary.

A pair $(i,j)$ with $i < j$ is counted if sequence $i$ and sequence $j$ are complementary.

Constraints

$1 \le n \le 10^5$
$1 \le |s_i| \le 100$
Each character is one of $\{A, C, G, T\}$

Input

\begin{array}{l} n \\ s_0 \\ s_1 \\ \vdots \\ s_{n-1} \end{array}

Output

$ans$

Samples

Input

3
ACGT
TGCA
AAAA

Explanation

The complement of ACGT is TGCA (A $\to$ T, C $\to$ G, G $\to$ C, T $\to$ A). So (ACGT, TGCA) form a complementary pair. AAAA's complement is TTTT, which is not present. Answer: 1.

Output

Input

4
AAA
TTT
AAA
TTT

Explanation

The complement of AAA is TTT. Complementary pairs: (AAA at index 0, TTT at index 1), (AAA at index 0, TTT at index 3), (AAA at index 2, TTT at index 1), (AAA at index 2, TTT at index 3). Answer: 4.

Output

Input

5
AT
TA
CG
GC
AA

Explanation

Complement of AT is TA, so (AT, TA) is a pair. AT is also the complement of TA, counted once. Complement of CG is GC, so (CG, GC) is a pair. AA's complement is TT which is not present. Answer: 2.

Output

Given $n$ DNA sequences (strings over the alphabet $\{A, C, G, T\}$ ), count the number of complementary pairs.

Two DNA sequences are complementary if they have the same length and at every position, the characters are complements: $A \leftrightarrow T$ and $C \leftrightarrow G$ .

For example, $\texttt{ACGT}$ and $\texttt{TGCA}$ are complementary. $\texttt{AAA}$ and $\texttt{TTT}$ are complementary.

A pair $(i,j)$ with $i < j$ is counted if sequence $i$ and sequence $j$ are complementary.

Constraints

$1 \le n \le 10^5$
$1 \le |s_i| \le 100$
Each character is one of $\{A, C, G, T\}$

\begin{array}{l} n \\ s_0 \\ s_1 \\ \vdots \\ s_{n-1} \end{array}

$ans$

The complement of ACGT is TGCA (A $\to$ T, C $\to$ G, G $\to$ C, T $\to$ A). So (ACGT, TGCA) form a complementary pair. AAAA's complement is TTTT, which is not present. Answer: 1.