Xâu đối xứng

Tác giả:

Dạng bài

Điểm: 2000 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

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 × N\) cặp xâu. Bạn hãy đếm xem trong \(N×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

Bình luận

3

TCA_Khoa 12:13 p.m. 30 Tháng 8, 2020

rồi N = ? vậy ad

4

BeTapDi 9:02 p.m. 30 Tháng 8, 2020

tổng k quá 1e6 thì n <= 1e6 thôi :v

2 bình luận nữa