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

Цахиур Төмөр нэгж квадратуудаас тогтох тэгш өнцөгт өрөөнд байгаа бөгөөд тэрээр арван тавны цагдаа нараас зугтаж яваа ажээ. Нэг нүднээс зэргэлдээ дөрвөн нүд рүү шилжиж болдог (диагоналийн дагуу шилжихгүй). Мөрдөгчдөөс мултрахын тулд Төмөр аль болох чигээрээ явахгүй байх стратеги баримталж байгаа буюу боломж гарах бүрт зүүн эсвэл баруун гар тийш эргэнэ. 2 тал руу эргэх боломжгүй үед л чигээрээ явах ба хэзээ ч эсрэг чиглэл рүү буцаж эргэхгүй.
Төмөрийн байрлал болон өрөөний зураглал өгөгдсөн бол Төмөр зугтаж чадах эсэхийг тодорхойлж, зугтаж чадах (өрөөний захад хүрэх) тохиолдолд хамгийн багадаа хэр урт зам туулахыг ол.

Input

Эхний мөрөнд тестийн тоо t ( 1 ≤ t ≤ 100 ). Үүний дараа тест бүр нь дараах байдалтай байна.
• Өрөөний өндөр болон өргөн болох зайгаар тусгаарлагдсан h, w (1 ≤ h,w ≤ 80) тоонуудыг агуулсан мөр
• тус бүр нь w тэмдэгт агуулах h ширхэг мөр. Тэмдэгтүүд нь @(Төмөрийн байрлал), #(саад), .(хоосон зай) гэсэн тэмдэгтүүд байна.

Output

Тест бүрийн хувьд
• Хэрэв зугтах боломжтой бол өрөөний зах хүртэл явах замын хамгийн бага урт, үгүй бол -1 байна.

Example

Input:
2 
9 13
# # # # # # # # # # # # #
# @ . . . . . . . . . . #
# # # # # . # . # . # . #
# . . . . . . . . . . . #
# . # . # . # . # . # . #
# . # . . . . . . . # . #
# . # . # . # . # . # . #
# . . . . . . . . . . . #
# # # # # . # # # # # # #
4 6
# . # # # #
# . # . # #
# . . . @ #
# # # # # #


Output:
31
-1