Zolaq#1537

Zolaq

1 saniyə

128 meqabayt

Çox asan

Uzunluğu $1 \times n$ 1 \times n olan, $1 \times 1$ 1 \times 1 ölçülü hücrələrə bölünmüş düzbucaqlı verilib. Hər bir hücrə ağ və ya qara rəngdə boyana bilər.

Bu düzbucaqlığın kodu soldan sağa baxıldıqda ard-arda gələn qara hücrələrin sayına bərabər olan ədədlər ardıcıllığıdır.

Məsələn, yuxarıda göstərilən düzbucaqlığın kodu $23281$ şəklindədir. Koddakı ağ hücrələrin sayı nəzərə alınmır; qara hücrələr qruplarının hər biri növbəti qrupdan ən az bir ağ hücrə ilə ayrılmalıdır. Beləliklə, eyni koda bir neçə fərqli düzbucaqlı uyğun gələ bilər. Xüsusilə, aşağıdakı düzbucaqlığa da verilmiş kod uyğun gəlir:

Verilmiş koda uyğun gələn düzbucaqlıların sayını müəyyən edin.

Giriş

Birinci sətirdə testlərin sayı $t (1 < t < 20)$ t~(1 < t < 20) verilib. Növbəti $t$ sətirdən hər biri ayrılıqda bir test olub:

düzbucaqlığın uzunluğunu $n (1 \leq n \leq 200)$ n~(1 \le n \le 200);
kodda olan ədədlərin sayını $k (0 \leq k \leq \frac{n + 1}{2})$ k~(0 \le k \le \frac{n+1}{2});
kodu təsvir edən $k$ ədəd.

Çıxış

Hər bir test üçün ayrıca bir sətirdə verilmiş koda uyğun gələn düzbucaqlıların sayını çıxış edin.

Nümunələr

Nümunə 1

Loading

1 \times n

1 \times 1

t (1 < t < 20)

n (1 \leq n \leq 200)

k (0 \leq k \leq \frac{n + 1}{2})