Програмчлалын олимпиадын бодлогын архив

Мандах програмаа зүгшрүүлэлт хйиж байхдаа түүний прогрмын алдаа нь санах ойд байгаа "квадрат устгагч"-тай холбоотой байж болохыг ажиглажээ. Санах ой нь зөвхөн тэг ба нэгээс тогтсон R мөр ба C баганаас тогтоно. Квадрат устгагч бол нэгээс олон тэмдэгтээс бүрдсэн санах ойн квадрат дэд матриц бөгөөд түүнийг 180 градус эргүүлэхэд яг хэвээр байдаг. Жишээ нь, дараах матриц 3 квадрат устгагчтай.

101010
111001
101001
Санах ой

....10
....01
......
устгагч

......
...00.
...00.
устгагч

101...
111...
101...
устгагч

Хамгийн том хэмжээтэй квадрат устгагч ба түүний програм дахь алдааны хооронд холбоо байгаа эсэхийг Мандах мэдэхийг хүсчээ. Санах ойн зохион байгуулалт нь өгөгдсөн бол хамгийн том квадрат устгагчийн хэмжээг олдог програм зохиоход нь Мандахад тусална уу. Квадрат устгагчийн хэмжээ тухайн устгагчийн мөрийн эсвэл баганын тоо юм. Дээрх жишээнд устгагчийн хэмжээнүүд нь 2, 2, 3 юм.

Input

Оролт нь олон тестээс тогтоно. Эхний мөрөнд тестийн тоо Т байна. Дараагийн мөрүүдэд Т ширхэг тест байна. Тест бүр дараах бүтэцтэй: Тестийн эхний мөрөнд хоёр бүхэл тоо R ба С байна. (0 < R <= 300, 0 < C <= 300, 0 < T <= 7)Дараагийн R мөрөнд хоосон зайгүй С('0' эсвэл '1') тэмдэгт байна.

Output

Тест бүрийн тоогоор мөр болгонд хамгийн том устгагчийн хэмжээг хэвлэнэ, хэрэв квадрат устгагч байхгүй бол -1 хэвлэнэ.

Example

Input:
3
3 6
101010
111001
101001
4 5
10010
01010
10101
01001
3 3
101
111
100


Output:
3
3
-1