给定 $$$n$$$ 字符串,每个长度为 $$$2$$$,由从 'a' 到 'k' 的小写拉丁字母组成,输出索引对 $$$(i, j)$$$ 的数量,使得 $$$i < j$$$ 并且第 $$$i$$$ 字符串和第 $$$j$$$ 字符串在一个位置上完全相同。
换句话说,计算对 $$$(i, j)$$$ ($$$i < j$$$) 的数量,使得第 $$$i$$$ 字符串和第 $$$j$$$ 字符串恰好有一个位置 $$$p$$$ ($$$1 \leq p \leq 2$$$) 使得 $$${s_{i}}_{p} \neq {s_{j}}_{p}$$$。
答案可能不适合 32 位整数类型,因此您应该使用 64 位整数,例如 C++ 中的 long long 以避免整数溢出。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 字符串的数量。
接下来是 $$$n$$$ 行,其中第 $$$i$$$ 包含长度为 $$$2$$$ 的单个字符串 $$$s_i$$$,由从 'a' 到 'k' 的小写拉丁字母组成。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,打印一个整数 - $$$(i, j)$$$ ($$$i < j$$$) 的对数,使得第 $$$i$$$ 字符串和第 $$$j$$$ 字符串恰好有一个位置 $$$p$$$ ($$$1 \leq p \leq 2$$$) 使得 $$${s_{i}}_{p} \neq {s_{j}}_{p}$$$。
请注意,某些测试用例的答案不适合 32 位整数类型,因此您应该在编程语言中至少使用 64 位整数类型(例如 C++ 的 long long)。
示例
输入 #1
4 6 ab cb db aa cc ef 7 aa bb cc ac ca bb aa 4 kk kk ab ab 5 jf jf jk jk jk
输出 #1
5 6 0 6
注意
对于第一个测试用例,仅在一个位置不同的对是:(“ab”,“cb”),(“ab”,“db”),(“ab”,“aa”),(“cb”,“db”)和(“cb”,“cc”)。
对于第二个测试用例,仅一个位置不同的对是:(“aa”,“ac”),(“aa”,“ca”),(“cc”,“ac”),(“cc”,“ca”),(“ac”,“aa”)和(“ca”,“aa”)。
对于第三个测试用例,没有满足条件的对。