Ağ və qara rəngdə olmaqla n sayda qutu bir sırada düzülüb. Bu qutular soldan-sağa 1-dən n-ə ədələrlə nömrələnmişdir. Barış qutulara nəzər yetirdikdə qara qutudan dərhal sonra gələn ağ qutu gördükdə qıcıqlanır. Buna görə də o sizdən bütün ardıcıl {qara, ağ} qutu cütlərində, qutuların yerini dəyişdirməyi xahiş etdi.

Bir mərhələdə siz hazırkı vəziyyətdə bütün {qara, ağ} qutu cütlərini müəyyən edirsiniz və daha sonra onların hər birində yerdəyişmə edirsiniz. Lakin bir mərhələdən sonra yenə də ardıcıl gələn {qara, ağ} qutu cütləri mövcud ola bilər. Belə olan halda siz yenidən eyni prosesi təkrarlamalısınız.

Neçə mərhələdən sonra ardıcıl gələn {qara, ağ} qutu cütü olmayacaq?

Giriş verilənləri

Birinci sətirdə bir tam ədəd t – testlərin sayı verilir.

Daha sonra t sayda testin hər birində birinci sətirdə bir tam ədəd n, ikinci sətirdə n sayda tam ədəd pi-lər verilir.

Burada pii-ci qutunun rəngidir. pi = 1 qara, pi = 0 ağ rəngi bildirir.

Çıxış verilənləri

Çıxışa hər bir test üçün məsələnin şərtində soruşulan mərhələlərin sayını yeni sətirdən verin.

Məhdudiyyətlər

• 1 ≤ t ≤ 100
• 1 ≤ n ≤ 104
• pi = 0, 1

Alt tapşırıqlar

Bu məsələ aşağıdakı kimi 2 alt tapşırıqdan ibarətdir: