题目描述

给定环状 01 字符串 $s$，即假设字符串最后一个字符与第一个字符相邻。

你可以进行任意多次操作，每次操作将序列中所有子串 "01"（显然这些子串两两不交）替换为 "10"。

问可以生成多少种不同的字符串。

多组询问。

输入格式

第一行一个整数 $T(1\le T\le 10^6)$，表示询问组数。

接下来 $T$ 行，每行一个 01 字符串，表示一组询问。

输出格式

$T$ 行，每行一个整数，表示一组询问的答案。

样例

见下发文件。

数据范围

$1\le T\le 10^6,1\le |s|\le 10^6,\sum |s|\le 10^7$

有 $10\%$ 的数据满足 $\sum|s|\le 5000$。