Kərpiclər

Verilmiş ardıcıllıq ağ (W) və qara (B) kərpiclərdən ibarətdir. Bu ardıcıllığı elə boş olmayan bloklar şəklində bölməlisiniz ki, hər blokda ağ və qara kərpiclərin nisbəti eyni olsun.

Ardıcılığı həmişə bir bloka "bölmək" mümkündür (bu bizim üçün maraqlı deyil). Biz mümkün qədər çox blok əldə etmək istəyirik. Aşağıdakı ardıcıllıqlara və onların bölünmələrinə baxaq:

• BWWWBB = BW + WWBB (nisbət 1:1),

• WWWBBBWWWWWWWWWB = WWWB + BBWWWWWW + WWWB (nisbət 3:1).

Hər iki bölünmə blokların sayına görə optimaldır.

Giriş məlumatları

Birinci sətir testlərin sayını t göstərir.

Hər bir test n ədədindən (1 ≤ n ≤ 10^5) - ardıcıllığın uzunluğundan başlayır. Növbəti n sətirin hər biri k ədədini (1 ≤ k ≤ 10^9) və W və ya B simvollarından birini ehtiva edir, ardıcıllıqda müəyyən rəngdə k kərpic olduğunu göstərir. Ümumi kərpic ardıcıllığının uzunluğunun 10^9-dan çox olmadığı təmin edilir.

Çıxış məlumatları

Hər bir test üçün axtarılan ən çox blok sayını ayrıca sətirdə çıxarın.