Сәулет өнері көбінесе екі дарынды, бірақ көзқарастары қарама-қайшы ойшылдың қақтығысынан туады. Жаңа қалалық серуен жолының бас сәулетшілері Котори мен Уми төсеніштің эстетикалық бағытына қатысты тығырыққа тірелді. Серуен жолы бір қатарда орналасқан $n$ ұяшық тізбегі ретінде модельденеді.

Кейбір ұяшықтарға тас төселіп қойған: кейбіреуінде Которидің қолтаңбасына айналған ақ мәрмәр болса, басқаларында Уми ұнататын қара гранит жатыр. Көптеген ұяшықтар әлі де бос («?» белгісімен белгіленген). Енді Котори мен Уми қалған ұяшықтарды біртіндеп толтыруы керек.

Ынтымақтастықта толық әділдікті қамтамасыз ету және ешбір философияның күрессіз үстемдік етуіне жол бермеу үшін олар ресми жобалау хаттамасына келісті:

• Котори мен Уми кезекпен бос ұяшыққа бір тастан қояды, ойынды Котори бастайды.
• Котори әрқашан ақ мәрмәр тасты қояды, өйткені ол серуен жолының сұлулығы ақ мәрмәрдің ең ұзын тұтас кесіндісімен өлшенеді деп есептейді. Әрине, ол осы ұзындықты барынша арттыруға тырысады.
• Құрылымдық контраст пен ырғақ беруді көздейтін Уми ұзын, үздіксіз ақ бөліктерді бірсарынды деп санайды. Ол сол максималды ұзындықты барынша азайту мақсатында әрқашан қара гранит тасты қояды.

Тас қойылғаннан кейін оны жылжытуға немесе ауыстыруға болмайды. Бұл процесс барлық бос ұяшықтар толтырылғанша жалғасады.

Серуен жолының бастапқы күйі берілген. Екі сәулетші де өздерінің эстетикалық мақсаттарына жету үшін оңтайлы ойнайды деп есептеп, қорытынды «Эстетикалық ұпайды» — ақ мәрмәрдің ең ұзын тұтас кесіндісінің ұзындығын — анықтау сіздің міндетіңіз.

Кіріс деректер

Бірнеше тест жиынтығы берілген. Кіріс деректердің бірінші жолында тест жиынтықтарының санын білдіретін бүтін сан $T$ ($1 \le T \le 10^4$) берілген. Әрбір тест жиынтығы үшін:

Бірінші және жалғыз жолда ұзындығы $n$ ($1 \le n \le 10^5$) болатын бір жол $s_1 s_2 \dots s_n$ берілген, мұндағы:

• 0 — ішінде Которидің ақ мәрмәрі бар ұяшықты білдіреді;
• 1 — ішінде Умидің қара граниті бар ұяшықты білдіреді;
• ? — қазіргі уақытта бос ұяшықты білдіреді.

Барлық тест жиынтықтары бойынша $n$ қосындысы $10^6$-нен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жиынтығы үшін ойынның қорытынды есебін білдіретін бүтін санды бір жолға шығарыңыз.

Мысалдар

Кіріс деректер 1

6
??
000
111
0??0??0
0?0?0?0
00?00?100?0

Шығыс деректер 1

1
3
0
3
5
5