Số xâu con tốt

Cho một xâu nhị phân $s$ (mỗi ký tự là 0 hoặc 1).

Gọi $f(t)$ là giá trị thập phân của số được biểu diễn ở hệ nhị phân bởi xâu $t$ (cho phép có các chữ số 0 đứng đầu). Ví dụ: $f(\text{011})=3$, $f(\text{00101})=5$, $f(\text{10})=2$, $f(\text{000})=0$, $f(\text{000100})=4$.

Một xâu con liên tiếp $s_l{s}_{l+1}\dots s_r$ được gọi là tốt nếu

$$r-l+1=f(s_l{s}_{l+1}\dots s_r).$$

Tức là độ dài của xâu con đúng bằng giá trị thập phân của nó khi đọc như số nhị phân (cho phép có các chữ số 0 đứng đầu).

Cho $t$ truy vấn độc lập, với mỗi xâu $s$ hãy đếm số xâu con tốt của $s$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ — số truy vấn.
• Mỗi dòng tiếp theo chứa một xâu $s$ chỉ gồm các ký tự 0 và 1.

Dữ liệu ra

Với mỗi truy vấn, in ra một dòng chứa số xâu con tốt của $s$.

Ràng buộc

• $1\le t\le 1000$
• $1\le |s|\le 2·{10}^5$
• $\sum |s|\le 2·{10}^5$

Ví dụ