Šeštadieninė informatikos olimpiadininkų mokykla

Spėlionė yra Andriaus mėgstamiausias žaidimas. Jam naudojama kaladė kortų, ant kiekvienos kortos yra užrašyta po seką, sudarytą iš nulių ir vienetų. Visos ant kortų užrašytos sekos yra vienodo ilgio. Andrius pasirenka vieną kortą iš kaladės, o kitas žaidėjas bando nustatyti, kokią kortą jis pasirinko, užduodamas klausimus "Koks yra i-asis ant kortos užrašytos sekos skaitmuo?" Po kiekvieno klausimo, Andrius atsako (teisingai), ir antrasis žaidėjas gali arba užduoti dar vieną klausimą, arba spėti Andriaus pasirinktą kortą. Jis gali spėti tik vieną kartą, jei pataiko - jis laimi, jei nepataiko - pralaimi. Andrius dabar žaidžia šį žaidimą su jumis. Žinodami visas ant kortų esančias sekas, pasakykite, kiek mažiausiai klausimų reikia užduoti, kad nustatytumėte ant Andriaus parinktos kortos užrašytą seką, nepriklausomai nuo to, kurią kortą jis pasirinko.

Įvestis

Pirmoje eilutėje bus skaičius z (1 ≤ z ≤ 20) - testų skaičius. Toliau aprašyti testai. Kiekvieno testo pirmoje eilutėje bus skaičiai n, k (1 ≤ n ≤ ; 1 ≤ k ≤ 13), nurodantys kortų skaičių ir ant jų parašytų sekų ilgį. Kitose n eilučių bus sekos, susidedančios iš vienetų ir nulių, nurodančios sekas, esančias ant kortų. Jokios dvi sekos viename teste nesutaps.

Išvestis

Kiekvienam testui išspausdinkite vieną skaičių - kiek mažiausiai klausimų reikės užduoti, kad laimėtumėte žaidimą.

Pavyzdžiai

1
4 3
000
100
010
011

2