Нам потрібно більше менеджерів!
Медіакомпанія, в якій ви працюєте, планує змінити свою організаційну структуру з безначальницької на ієрархічну. Буде призначено генерального директора, якому підпорядковуватимуться всі інші співробітники, безпосередньо або через інших. Кожен співробітник, окрім генерального директора, матиме рівно одного безпосереднього керівника. Оскільки така реформа може викликати конфлікти між працівниками, ваша компанія прагне обрати таку ієрархію, яка мінімізує соціальні витрати для фірми.
Кількість розбіжностей між двома колегами, які змушені вступити у відносини начальник - підлеглий, пропорційна кількості політичних питань, з яких вони не згодні. У вашій компанії кожен співробітник має чіткі погляди на кожну з n найпоширеніших політичних тем: у кожній з n категорій думки співробітника можуть бути або лівими, або правими. Що ще гірше, немає двох співробітників з однаковими переконаннями. Вартість безпосереднього підпорядкування одного співробітника іншому дорівнює кількості тем, з яких вони не згодні. Вартість нової організаційної структури дорівнює сумі витрат на тертя між кожними двома співробітниками, де один безпосередньо підпорядковується іншому. Ваше завдання - розрахувати мінімально можливу вартість нової структури.
Вхідні дані
Перша строка містить кількість тестів z (1 ≤ z ≤ 10). Далі йде опис тестів.
Кожен тест починається з двох цілих чисел n і m (1 ≤ n ≤ 20, 1 ≤ m ≤ 2^n) - кількість тем, з яких працівники мають думку, і кількість працівників. Кожен з наступних m рядків містить політичні погляди одного працівника. Опис поглядів працівника являє собою рядок, що складається з n літер. Якщо i-им є символ L (R), то працівник має лівий (правий) погляд на i-у тему.
Вихідні дані
Для кожного тесту виведіть рядок, що містить одне число - мінімальну вартість ієрархії управління.