Facebook Hacker Cup 2013. Бодлого АААААА

AAAAAA
Элийн тоглоомын газрыг AAAAAA гэдэг ба хүмүүс маш ихээр ирдэг.
Үйлчлүүлэгчид машины зогсоол дээр урт дараалал үүсгэн зогсдог. Эл аль болох олон хүнийг зогсоол дээрээ багтаахыг хүсч байгаа. Харин хүмүүс хэтэрхий их мушгиралдсан дараалалд зогсохыг хүсдэггүй.
Зогсоолыг тэгш өнцөгт хэлбэртэй бөгөөд нүднүүдээс тогтоно гэж үзэж болно. Орох хаалга нь зүүн дээд талын буланд байрлана. Бүх дараалал эндээс эхэлнэ. Зогсоол дээр машинууд байж болох ба тэдгээрийг ‘#’ тэмдгээр тэмдэглэнэ. Үйлчлүүлэгчид машин дээр гарч чадахгүй. Бусад нүднүүдэд ‘.’ тэмдэгт байрлана. Хэрэглэгчдийн хүсэлтээр дараалал үргэлж доош болон баруун чиглэлд үргэлжилнэ. Мөн хэрэглэгчид нь нэг буулт хийсэн нь нэг дараалалд ганц ширхэг, үргэлжилсэн дээш чиглэсэн хэсэг эсвэл ганц ширхэг зүүн тийш чиглэсэн үргэлжилсэн хэсгийн аль нэг нь байж болно гэсэн нөхцөл юм. Энэ хоёр үргэлжилсэн хэсэг нэг дараалалд хоёулаа байж болохгүй.
Дараалал нь эдгээр дөрвөн чиглэлд л үргэлжилнэ. Диагоналиар явахгүй.
Сул зай бүрт ганц л үйлчлүүлэгч багтах ба дараалсан хоёр үйлчлүүлэгч хоорондоо хөрш нүднүүдэд байрлана. Дараалсан хоёр үйлчлүүлэгч хоорондоо зайтай, тасарсан байж болохгүй.
Оролт
Эхний мөрөнд тестийн тоо болох Т бүхэл тоо байрлана.
Тест бүрийн эхний мөрөнд тэгш өнцөгтийн мөр болон баганын тоог илэрхийлэх N, M бүхэл тоонууд өгөгдөнө.
Дараагийн N ширхэг мөрөнд яг M ширхэг тэмдэгт бүхий тэмдэгт мөр байрлана.
Гаралт
i-р тест бүрийн хувьд зүүн дээд өнцгөөс эхлэн байрлуулж болох хамгийн урт дарааллын хэмжээг “Case #i: “ гэсний дараа гаргана.
Хязгаарлалт
1<=T<=20 1<=N, M<=500 Тэгш өнцөгт дэх тэмдэгтүүд ‘#’ эсвэл ‘.’ байна. Зүүн дээд булангийн тэмдэгт дандаа ‘.’ байна.

Жишээ оролт
5
5 5
.....
.....
.....
.....
.....
1 10
..........
5 5
...#.
...#.
...#.
...#.
.....
3 3
..#
#.#
...
3 8
........
#.#.#.#.
#.#.#.#.
Жишээ гаралт
Case #1: 17
Case #2: 10
Case #3: 17
Case #4: 5
Case #5: 10