Poddavki#3713
Çox vaxt maraqlı bir oyun olduqda, onun motivləri əsasında "poddavki" oyunu daha maraqlı olur. "Poddavki"də, adətən, oyunun məqsədi ilkin qaydalara görə qəsdən uduzmaqdır. Bu məsələdə biz adi 8×8 taxtasında şahmat "poddavki"lərini nəzərdən keçirəcəyik, daha dəqiq desək, ağların yalnız bir neçə piyadası, qara isə bir vəzir qaldığı vəziyyəti.
Bizim vəziyyətimizdə ağlar birinci hərəkət edir. Öz növbəsində ağlar istənilən piyadanı seçir və onu irəli hərəkət etdirir. Əgər piyada ikinci üfüqi sıradadırsa, o, bir və ya iki hüceyrə irəli (şaquli olaraq) hərəkət edə bilər, əks halda yalnız bir hüceyrə irəli hərəkət edə bilər. Əgər piyada səkkizinci üfüqi sıraya çatarsa, daha hərəkət edə bilmir (bu məsələdə çevrilmə icazə verilmir). Piyada diaqonal üzrə bir hüceyrə vurur, bu halda götürmə məcburidir və oyun bitir. Əgər ağların icazə verilən hərəkətləri yoxdursa, oyun da bitir.
Qaralar öz yeganə vəziri ilə hərəkət edir. Əgər qaralar heç bir piyadanı yeyə bilmirsə, oyun bitir. Əks halda qaralar istənilən piyadanı seçir və onu yeyir.
Bu oyunda ağlar mümkün qədər çox piyadanı verməyə çalışır, qaralar isə mümkün qədər az yeməyə çalışır. Sizin vəzifəniz - ağların maksimum neçə piyadanı verə biləcəyini öyrənməkdir.
Giriş faylının birinci sətirində test dəstlərinin sayı T (1 ≤ T ≤ 5) verilmişdir. Sonra hər bir dəstin təsviri olan T sətir gəlir. Dəst n (1 ≤ n ≤ 8) və n+1 sahə koordinatları ilə verilir, ilk n ağ piyadaları, sonuncu isə qara vəzirin mövqeyini göstərir.
Heç bir iki ağ piyada eyni şaquli sırada durmur. Qara vəzir bütün ağ piyadaların mövqeyindən fərqli bir mövqedə durur.
Hər bir test dəsti üçün, hər iki tərəfin optimal oyununda ağların verə biləcəyi maksimum piyadaların sayını çıxarın.
Nümunə 1