你所在的媒体公司打算将扁平化的组织结构（没有上司）替换为层级结构。公司将选出一名首席执行官（CEO），其他所有人直接或间接地向其汇报。除 CEO 外，每位员工都有且仅有一名直接上司。由于这种改革必然会在员工之间产生摩擦，公司的目标是选择一种能使公司社会成本最小化的层级结构。

在上下级关系中，两名员工之间的摩擦程度与他们在政治议题上的分歧数量成正比。在你的公司中，每位员工对 $n$ 个最常见的政治议题都有非常坚定的看法：在每个类别中，员工的观点要么是左派，要么是右派。更糟糕的是，没有两名员工的观点完全相同。一名员工直接向另一名员工汇报的成本等于他们分歧的议题数量。新组织结构的成本是所有存在直接上下级关系的员工对之间的摩擦成本之和。你需要计算新结构可能产生的最小成本。

输入格式

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

每个测试用例包含两个整数 $n$ 和 $m$ ($1 \le n \le 20, 1 \le m \le 2^n$)，分别表示员工有观点的议题数量和员工人数。接下来有 $m$ 行，每行描述一名员工的政治观点。员工观点的描述是一个由 $n$ 个字母组成的字符串。如果第 $i$ 个字符是 'L'（'R'），则该员工在第 $i$ 个议题上持左派（右派）观点。

输出格式

对于每个测试用例，输出一行，包含一个整数，即管理层级结构的最小成本。

样例

输入格式 1

1
5 4
LLLLL
LLLLR
RRRRL
RRRRR

输出格式 1

6