13:I[87,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"Header"] 14:I[1742,["736","static/chunks/89fc4f0e-9e200ae6a0166583.js","401","static/chunks/363642f4-32903b9154b7835a.js","153","static/chunks/153-58eddeb032cc4608.js","131","static/chunks/131-05ce00cfd760e12b.js","87","static/chunks/87-b76b60eef573119a.js","286","static/chunks/app/problem/%5Bid%5D/page-45cf3875257fc32e.js"],"ProblemView"] 15:T698,

You are given a binary string $$$s$$$ (recall that a string is binary if each character is either $$$0$$$ or $$$1$$$).

Let $$$f(t)$$$ be the decimal representation of integer $$$t$$$ written in binary form (possibly with leading zeroes). For example $$$f(011) = 3, f(00101) = 5, f(00001) = 1, f(10) = 2, f(000) = 0$$$ and $$$f(000100) = 4$$$.

The substring $$$s_{l}, s_{l+1}, \dots , s_{r}$$$ is good if $$$r - l + 1 = f(s_l \dots s_r)$$$.

For example string $$$s = 1011$$$ has $$$5$$$ good substrings: $$$s_1 \dots s_1 = 1$$$, $$$s_3 \dots s_3 = 1$$$, $$$s_4 \dots s_4 = 1$$$, $$$s_1 \dots s_2 = 10$$$ and $$$s_2 \dots s_4 = 011$$$.

Your task is to calculate the number of good substrings of string $$$s$$$.

You have to answer $$$t$$$ independent queries.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of queries.

The only line of each query contains string $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$), consis

The Number Of Good Substrings

Examples