Xâu đối xứng

Một xâu được gọi là đối xứng nếu đọc từ trái qua phải và đọc từ phải qua trái đều giống nhau.

Ví dụ xâu "aba", "abba" là xâu đối xứng; còn xâu "abc", "abca" thì không.

Bạn được cho \(N\) xâu, như vậy sẽ có \(N \times N\) cặp xâu. Bạn hãy đếm xem trong \(N \times N\) cặp xâu này, có bao nhiêu cặp mà khi nối xâu thứ hai vào sau xâu thứ nhất sẽ cho ra một xâu đối xứng.

Input

Dòng đầu ghi một số \(N\).
\(N\) dòng sau mỗi dòng mô tả một xâu, bắt đầu là độ dài của xâu, sau đó là một dấu cách và tiếp theo là nội dung của xâu. (Xâu chỉ gồm các chữ cái latin thường và có độ dài nguyên dương)

Dữ liệu vào luôn đảm bảo tổng độ dài các xâu không quá 1000000

Output

Ghi ra một số duy nhất là số cặp xâu tìm được.

Example

Test 1

Input

3
1 a
2 ab
2 ba

Output

Thông tin bài

Điểm:

100

Thời gian:

1.0s

Bộ nhớ:

256M

Input:

bàn phím

Output:

màn hình

Ngày tạo:

02/08/2026

Tác giả:

root

Điều hướng chính

Ngôn ngữ

Phím tắt

Input

Output

Example

Bình luận