个人快速编程竞赛（IFPC）今年的注册人数创下了纪录——共有 $n$ 名参赛者。你的任务是为他们设置账户。每个账户都有一个别名，即用户名。IFPC 系统仅接受由小写英文字母和数字组成的别名。

为了不弄乱，你根据参赛者的名字和姓氏创建别名，遵循相同的算法：取名字的前 $a$ 个字母，然后取姓氏的前 $b$ 个字母，最后加上你选择的 $c$ 个数字。如果名字的长度不足 $a$ 个字母，或者姓氏的长度不足 $b$ 个字母，则直接取其全部字母（此时别名会更短，但这没关系）。例如，当 $a = b = c = 3$ 时，James Bond 可以获得别名 jambon007，而 Lady Di 可以获得别名 laddi123。

你希望别名尽可能短，以节省内存。另一方面，所有参赛者必须拥有唯一的别名。对于给定的参赛者列表（他们的名字和姓氏），请找到 $a, b$ 和 $c$，使得所有参赛者都能拥有唯一的别名，且 $a + b + c$ 的值尽可能小。数字 $a, b$ 和 $c$ 可以为 $0$（但不能同时为 $0$——别名不能为空）。

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 6$)。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 200\,000$)，表示参赛者人数。接下来的 $n$ 行包含参赛者的名字和姓氏。名字和姓氏均仅由小写英文字母组成。

单个测试用例中所有名字和姓氏的长度总和不超过 $1\,500\,000$。两名参赛者可能拥有相同的名字和姓氏（他们仍然需要获得不同的别名）。

输出格式

对于每个测试用例，输出三个非负整数 $a, b$ 和 $c$，使得你可以创建唯一的别名，且 $a + b + c$ 的值最小。

如果存在多个使总和最小的解，你可以输出其中任意一个。

样例

样例输入 1

1
11
sven eriksson
erik svensson
sven svensson
erik eriksson
bjorn eriksson
bjorn svensson
bjorn bjornsson
erik bjornsson
sven bjornsson
thor odinsson
odin thorsson

样例输出 1

1 1 0

说明

通过取所有参赛者的首字母（名字和姓氏的第一个字母：se, es, ss, ee, ...）可以获得唯一的别名。答案 1 0 1 也是正确的，因为你可以通过在每个人的名字首字母后添加一个数字来创建唯一的别名。