시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB124250.000%

문제

In the attic of grandparents’ home Neringa has found a set of cards. Each card has four capital Latin letters written on it as a $2 \times 2$ grid. The set has $N$ cards and all of them are distinct.

Neringa noticed that some cards may be placed next to each other so that the pairs of letters on both cards adjacent to the connecting edge would be identical.

Let’s call the pairs of cards that could paired in the way described above as matching. To match a pair of cards it is allowed to move them but not allowed to rotate or flip. A card can form multiple matching pairs.

and match: ,

and match: , , , ,

and do not match.

Figure 1: Matching and not matching pairs of cards. The second pair of cards can be matched in four different ways.

Calculate the amount of matching card pairs in the card set discovered by Neringa.

입력

The total amount of cards $N$ is given in the first row.

The remaining $2N$ rows describe the cards. Each of the rows contains two capital Latin letters. One card is described by two consecutive input rows.

출력

Output the amount of matching card pairs.

제한

  • $1 ≤ N ≤ 26^{4} = 456\,976$

서브태스크

번호배점제한
116

Each card has at least three A letters

220

$N ≤ 2500$

320

$N ≥ 26^4 - 2500$

419

Each card has four different letters

525

No additional constraints

예제 입력 1

3
IO
OI
AA
AA
OI
IO

예제 출력 1

1

Even though the first and the third cards could be matched in four different ways, they still make only one matching pair. The second card cannot be matched with itself.

예제 입력 2

2
QW
XZ
AB
CD

예제 출력 2

0

No matching pairs.

채점 및 기타 정보

  • 예제는 채점하지 않는다.