The media company you are working at intends to replace its at organisational structure (no bosses) with a hierarchical one. A CEO will be chosen, to whom everyone else, directly or indirectly, is going to report. Every other employee is going to have exactly one direct supervisor. As such a reform is bound to introduce friction between workers, your company's goal is to choose a hierarchy that minimises social costs for the firm.

The amount of friction between two coworkers forced into a superior-subordinate relationship is proportional to the number of political issues they disagree on. In your company, every employee has very resolute views on each of the n most common political topics: in each of the n categories, an employee's opinions can be either leftist or rightist. To make matters worse, no two employees have identical beliefs. The cost of having one employee directly report to another is equal to the number of topics they disagree on. The cost of the new organisational structure is the sum of the costs of friction between every two employees such that one is (directly) managed by the other. You are asked to compute the minimum possible cost of the new structure.

Input

The first line contains the number of test cases z (1 ≤ z ≤ 10). The descriptions of the test cases follow.

Every test case consists of two integers n and m (1 ≤ n ≤ 20, 1 ≤ m ≤ 2n) - the number of topics the workers have an opinion on and the number of employees, respectively. Next, m lines follow, each describing the political opinions of one worker. The description of worker's views is a string consisting of n letters. If the i-th character is L (R), the worker has leftist (rightist) views on the i-th subject.

Output

For each test output a line containing a single integer - the minimum cost of the management hierarchy.