Evə gedirəm

Korova Bessi sevdiyi otlaqdan anbara gedir.

Otlaq və anbar n * n ölçülü bir şəbəkədə yerləşir; otlaq sol üst küncdə, anbar isə sağ alt küncdədir. Bessi anbara mümkün qədər tez çatmaq istəyir, buna görə də yalnız aşağı və sağa hərəkət edir. Bəzi hüceyrələrdə Bessi ətrafından keçməli olduğu ot tayaları var.

Bessi özünü yorğun hiss edir, buna görə də hərəkət istiqamətini ən çox k dəfə dəyişmək istəyir.

Bessinin otlaqdan anbara neçə fərqli yolu var? İki yol fərqli hesab olunur, əgər Bessi bir yolda müəyyən bir hüceyrədən keçirsə və digər yolda keçmirsə.

Giriş məlumatları

Birinci sətir t (1 ≤ t ≤ 50) testlərinin sayını ehtiva edir. Hər bir test n (2 ≤ n ≤ 50) və k (1 ≤ k ≤ 3) olan sətirlə başlayır.

Sonrakı n sətirin hər biri n simvoldan ibarət sətirdir. Hər bir simvol ya hüceyrənin boş olduğunu göstərən ".", ya da ot tayasının olduğunu göstərən H simvoludur. Sol üst və sağ alt künclərin ot tayaları ilə dolu olmadığı təmin edilir.

Çıxış məlumatları

t sətir çıxarın, i-ci sətir i-ci subtest üçün Bessinin keçə biləcəyi fərqli yolların sayını göstərir.

Nümunə

Bessinin mümkün yollarını aşağı və sağa hərəkəti göstərən D və R simvollarından ibarət sətirlərlə təmsil edəcəyik.

Birinci subtestdə Bessinin iki yolu var: DDRR və RRDD.

İkinci subtestdə Bessinin 4 yolu var: DDRR, DRRD, RDDR, RRDD.

Üçüncü subtestdə Bessinin 6 yolu var: DDRR, DRDR, DRRD, RDDR, RDRD, RRDD.

Dördüncü subtestdə Bessinin 2 yolu var: DDRR, RRDD.

Beşinci və altıncı subtestlərdə Bessi anbara çata bilmir.

Yeddinci subtestdə 6 yol var: DDRDRR, DDRRDR, DDRRRD, RRDDDR, RRDDRD, RRDRDD.