F. Ahmad and Swapping Syndrome
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Ahmad has been reading a lot of blogs lately, and every time he sees two words next to each other starting with the same character he is fascinated.

Given an array $$$w$$$ of $$$n$$$ words, each consisting of lower-case English letters, what is the number of pairs $$$i, j$$$ such that $$$(1 \leq i \lt j \leq n)$$$ such that the words $$$w_i$$$ and $$$w_j$$$ next to each other fascinate Ahmad?

Input

The first line contains an 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 number of words in the array $$$w$$$.

The next line of each test case contains $$$n$$$ strings $$$w_1, w_2, \ldots, w_n$$$ $$$(1 \leq |w_i| \leq 13)$$$.

It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.

Output

For each test case, print the number of fascinating pairs.

Example
Input
3
3
atypical jpc ahmad
4
dive deep down drome
4
noomak noway jpc jcpcp
Output
1
6
2