시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 19 9 9 64.286%

문제

상근이는 전 세계에 존재하는 모든 크로스워드 퍼즐을 풀었다. 더 이상 풀 퍼즐이 없기 때문에, 새로운 퍼즐을 만드려고 한다.

단어의 길이가 같은 네 단어를 이용해서 정사각형 모양의 크로스워드 퍼즐을 만들 수 있다. 가로로 놓인 단어는 왼쪽부터 오른쪽으로 읽고, 세로로 놓은 단어는 위에서 아래로 읽는다. 아래 그림은 "HLAD", "NIVA", "HSIN", "DEDA"를 이용해서 만든 크로스워드 퍼즐의 한 예이다.

길이가 모두 같은 단어가 여러개 주어졌을 때, 서로 다른 정사각형 모양의 크로스워드 퍼즐을 몇 개나 만들 수 있는지 구하는 프로그램을 작성하시오. 한 단어는 꼭 한 번만 사용해야 한다. 두 정사각형이 적어도 한 위치에서 문자가 다르다면, 두 크로스워드퍼즐은 다른 퍼즐이다.

입력

첫째 줄에 단어의 개수 N이 주어진다. (4 ≤ N ≤ 100,000) 다음 N개 줄에는 알파벳 대문자로만 이루어진 단어가 주어진다. 단어의 길이는 모두 같으며, 10글자 이내이다.

출력

첫째 줄에 입력으로 주어진 단어를 이용해서 서로 다른 크로스워드 퍼즐을 몇 개나 만들 수 있는지 출력한다.

예제 입력

4
NIVA
HLAD
HSIN
DEDA

예제 출력

2

힌트