Медиакомпания, в которой Вы работаете, намерена заменить свою организационную структуру (без начальников) на иерархическую. Будет выбран генеральный директор, которому будут отчитываться все остальные - прямо или косвенно. У каждого другого сотрудника будет ровно один непосредственный руководитель. Поскольку такая реформа неизбежно приведет к возникновению трений между работниками, цель вашей компании - выбрать иерархию, минимизирующую социальные издержки для фирмы.

Количество разногласий между двумя коллегами, вынужденных вступать в отношения начальник - подчиненный, пропорционально количеству политических вопросов, по которым они не согласны. В вашей компании каждый сотрудник имеет очень решительные взгляды на каждую из n наиболее распространенных политических тем: в каждой из n категорий мнения сотрудника могут быть как левыми, так и правыми. Что еще хуже, нет двух сотрудников, имеющих одинаковые убеждения. Стоимость непосредственного подчинения одного сотрудника другому равна количеству тем, по которым они не согласны. Стоимость новой организационной структуры равна сумме затрат на трение между каждыми двумя сотрудниками, где один напрямую управляется другим. Вас просят рассчитать минимально возможную стоимость новой структуры.

Входные данные

Первая строка содержит количество тестов z (1 ≤ z ≤ 10). Далее следует описание тестов.

Каждый тест начинается двумя целыми числами n и m (1 ≤ n ≤ 20, 1 ≤ m ≤ 2n) - количество тем, по которым работники имеют мнение, и количество работников. Каждая из следующих m строк содержит политические взгляды одного работника. Описание взглядов рабочего представляет собой строку, состоящую из n букв. Если i - ым является символ L (R), то работник имеет левый (правый) взгляд на i - ую тему.

Выходные данные

Для каждого теста выведите строку, содержащую одно число - минимальную стоимость иерархии управления.