D. Manar's Birthday
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Manar is planning to open a coffee shop on her upcoming birthday. She wants to have a unique menu, but she's been extremely busy with all the preparations, so she has asked her friend for help. Her friend suggested that she could have drinks where the name is a palindrome formed by concatenating two words from a given array of strings. Manar liked this idea so much, so she's doing it!

Given an array of strings, find the number of distinct pairs of words $$$(s_i, s_j)$$$ such that $$$(i \neq j)$$$ and $$$s_i + s_j$$$ is a palindrome, where $$$(a + b)$$$ is the concatenation of string $$$a$$$ and string $$$b$$$.

A palindrome is a word, number, phrase, or other sequence of characters that reads the same backward as forward, such as "bananab" and "racecar".

Input

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the length of the array $$$s$$$.

The next line of each test case contains $$$n$$$ strings $$$s_1, s_2, \ldots, s_n$$$ $$$(1 \leq |s| \leq 4\cdot10^5)$$$ consisting of lowercase English letters, where $$$|s|$$$ denotes the length of the string $$$s$$$.

It's guaranteed that the sum of |s| over all test cases is not greater than $$$4\cdot10^5$$$.

Output

For each test case, output a single integer — the number of distinct pairs of words where their concatenation is a palindrome.

Example
Input
3
4
rak ka akar ak
3
abba abab aba
4
abc bac cba acb
Output
4
1
2