Peg Solitaire
Peg solitaire oyunu, Fransa kralı XIV Louis'in sarayında məşhur olan bir oyundur və aşağıdakı qaydalarla oynanır. İki ölçülü bir taxta verilir, hər bir dəlikdə bir mıx (çivi) ola bilər. Mıxın yeganə qanuni hərəkəti, yanındakı mıxın üzərindən boş dəliyə, onunla eyni sırada olan dəliyə, şaquli və ya üfüqi tullanmaqdır, bu zaman tullanılan mıx çıxarılır. Oyunun orijinal məqsədi, yalnız qanuni hərəkətlər edərək taxtada əvvəlcədən müəyyən edilmiş mövqedə tək bir mıx buraxmaq idi.
Aydındır ki, belə bir həll yalnız müəyyən taxta formaları və başlanğıc konfiqurasiyaları üçün mümkündür. Bu məhdudiyyəti aradan qaldırmaq üçün problemi bir qədər yenidən müəyyən edirik: Taxtanın başlanğıc konfiqurasiyası verildikdə, qanuni hərəkətlər vasitəsilə əldə edilə biləcək minimum mıx sayını və həmin mıx sayına çatmaq üçün tələb olunan minimum hərəkət sayını müəyyənləşdirin.
Giriş
Birinci sətir test hallarının sayı n (1 ≤ n ≤ 100) ehtiva edir. Hər bir test halı, solitaire taxtasının başlanğıc vəziyyətini təmsil edən aşağıdakı sətirlərlə təsvir olunur. Bu təmsildə '.' boş dəliyi, 'o' mıx olan dəliyi göstərir. '#' dəlik olmayan taxtanın bir hissəsini göstərir. Bütün taxtalar eyni formaya malikdir, nümunə girişinə baxın (dəliklərin mövqeyini ehtiva edir). Başlanğıc vəziyyətində taxtada ən çox 8 mıx ola bilər. İki ardıcıl test halı arasında boş bir sətir var.
Çıxış
Hər bir test halı üçün proqramınız bir sətirdə iki rəqəm çıxarmalıdır, bunlar bir boşluqla ayrılmışdır, birincisi verilmiş başlanğıc vəziyyətindən qanuni hərəkətlərlə əldə edilə biləcək minimum mıx sayını, ikincisi isə həmin mıx sayına çatmaq üçün tələb olunan minimum hərəkət sayını göstərir.