中等·Magry恼人的词典编辑

题目描述

最近Magry收到了任务：

给定n个单词（全部由小写字母组成），将给定的单词按如下规则排序：

1. 最后得到的排序顺序应为字典序非降序排列；
2. 只能通过不断交换相邻两个单词完成排序。

已知Magry每进行相邻两个单词的交换操作花费的代价为1，求排序最小代价。

输入

第一行为一个正整数$T$，代表有$T$组测试数据。

对于每组测试数据，第一行为一个正整数$n$，表示有$n$个单词。

接下来$n$行，每行一个长度不多于20的字符串（非空），表示待排序的单词序列。

保证$1 \leq T \leq 10$，$1 \leq n \leq 100,000$，每个单词仅包含小写字母。

输出

对于每组数据，输出一行，一个整数，排序最小代价。

输入样例

2
3
zoo
pen
apple
3
apple
banana
ask

输出样例

3
1

提示

求得的排序最小代价在long long范围内。