你目前正和一群朋友在滑雪旅行。总的来说，一切都很顺利：你白天享受滑雪的乐趣，晚上当然还有滑雪后的娱乐活动。然而，有一件烦心事：滑雪缆车。缆车一如既往地太小，每 5 秒钟只能运送一个人。更糟糕的是，你和你的朋友通常不会同时到达缆车处，这意味着你们在山脚下等缆车，以及在山顶等朋友时都要花费时间。

在山顶等待尤其低效。事实上，你意识到如果你的朋友还没到，你不如让其他人排在你前面。对你来说，这没什么区别，因为反正你都要在山顶等待。另一方面，如果某人的朋友已经到达并正在山顶等他，你的礼让行为可能会为他们节省时间。

你想知道如果每个人都采取这种友好的态度，总共能节省多少时间。你仔细观察了一段时间的队列，并注意到了哪些人属于同一个朋友圈。假设如果某人让另一个人插队不会改变他自己的总等待时间，但能为对方节省时间，那么他就会让对方插队。不断重复这个过程，直到无法再进行任何交换为止。总共能节省多少时间？

输入格式

第一行包含一个正整数：测试用例的数量，最多为 100 个。每个测试用例包含：

• 一行包含一个整数 $n$ ($1 \le n \le 25\,000$)：排队等候缆车的人数。
• 一行包含 $n$ 个字母数字字符（大写字母、小写字母和数字）：表示队列。该行中的第一个字符对应于队列最前面的人。相同的字符对应于同一朋友圈的人。

输出格式

每个测试用例输出一行：节省的总时间（以秒为单位）。

样例

输入 1

2
6
AABABB
10
Ab9AAb2bC2

输出 1

15
45