Ống Nghiệm

Bessie co hai ong nghiem, moi ong chua $N$ don vi chat long gom hai mau (mau 1 va mau 2). Chat long trong moi ong tao thanh cac lop (moi lop gom cac don vi cung mau lien tiep). Co ay muon tach rieng: moi ong chi chua mot mau. Co them mot coc trong de ho tro.

Mot "lan rot" la chuyen toan bo chat long cung mau o dinh cua mot binh sang binh khac. Muc tieu: tim so lan rot it nhat, va coc phai trong o cuoi.

Du lieu vao

• Dong 1: So nguyen $T$ ($1\le T\le 10$) -- so test case.

• Voi moi test case:

  • Dong 1: Hai so nguyen $N$ va $P$ ($1\le N\le {10}^5$).
  • Dong 2: Xau $N$ ky tu gom '1' va '2' -- ong nghiem 1 (tu day len dinh).
  • Dong 3: Xau $N$ ky tu gom '1' va '2' -- ong nghiem 2 (tu day len dinh).

• $P$ quyet dinh dang dau ra:

• $P=1$: Chi in so lan rot toi thieu $M$.
• $P=2$: In so $A$ ($M\le A\le M+5$), roi $A$ dong mo ta cac lan rot.
• $P=3$: In $M$, roi dung $M$ lan rot toi uu.

Du lieu ra

Theo dang tuong ung voi $P$. Moi lan rot ghi: nguon dich (1 = ong 1, 2 = ong 2, 3 = coc).

Rang buoc

• $1\le N\le {10}^5$
• Moi mau xuat hien it nhat 1 lan
• $T=10$

Vi du