Arsitektur sering kali merupakan hasil gesekan antara dua pemikiran cemerlang namun berlawanan. Kotori dan Umi, arsitek utama untuk jalan promenade metropolitan baru, mengalami jalan buntu terkait arah estetika trotoar tersebut. Promenade inidimodelkan sebagai barisan $n$ petak dalam satu baris tunggal.

Beberapa petak sudah dipasang batu: beberapa berisi marmer putih khas Kotori, sementara yang lain berisi granit hitam pilihan Umi. Banyak petak masih kosong (ditandai sebagai "?"). Kotori dan Umi sekarang harus mengisi petak yang tersisa satu per satu.

Untuk memastikan keadilan total dalam kolaborasi mereka dan mencegah satu filosofi mendominasi tanpa perjuangan, mereka telah menyepakati protokol desain resmi:

• Kotori dan Umi bergantian menempatkan satu batu ke dalam petak kosong, dengan Kotori jalan lebih dulu.
• Kotori selalu menempatkan batu marmer putih, karena ia percaya keindahan promenade diukur dari segmen berurutan terpanjang dari marmer putih. Ia tentu berusaha memaksimalkan panjang ini.
• Umi, yang berusaha memberikan kontras struktural dan ritme, percaya bahwa segmen putih panjang yang tak terputus itu monoton. Ia selalu menempatkan batu granit hitam, dengan tujuan meminimalkan panjang maksimum yang sama tersebut.

Begitu sebuah batu ditempatkan, batu tersebut tidak dapat dipindahkan atau diganti. Proses berlanjut hingga semua petak kosong terisi.

Diberikan keadaan awal promenade, tugas Anda adalah menentukan "Skor Estetika" akhir — panjang segmen berurutan terpanjang dari marmer putih — dengan asumsi kedua arsitek bermain secara optimal untuk mencapai tujuan estetika masing-masing.

Masukan

Terdapat beberapa kasus uji. Baris pertama masukan berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$) yang menyatakan banyaknya kasus uji. Untuk setiap kasus uji:

Baris pertama dan satu-satunya berisi sebuah string $s_1 s_2 \dots s_n$ dengan panjang $n$ ($1 \le n \le 10^5$), di mana:

• 0 menyatakan petak yang sudah berisi marmer putih Kotori;
• 1 menyatakan petak yang sudah berisi granit hitam Umi;
• ? menyatakan petak yang saat ini kosong.

Dijamin bahwa jumlah $n$ di semua kasus uji tidak melebihi $10^6$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi sebuah bilangan bulat yang menyatakan skor akhir permainan.

Contoh

Masukan 1

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

Keluaran 1

1
3
0
3
5
5