import java.io.*
import java.math.*
import java.text.*
import java.util.*
import java.util.regex.*

/*
 * Complete the twoTwo function below.
 */
fun twoTwo(a: String): Int {

    var count = 0

    for (i in 0 until a.length){
        for (j in (i + 1)..a.length){
            val currentNum = a.substring(i, j)
            val node = TREE.start(currentNum) ?: break
            if (node.find(currentNum)) count++
        }
    }

    return count
}

var TREE = MishaNode()
class MishaNode(var number: Char = '!', val childs: Array<MishaNode?> = Array(10){ null }, var flag: Boolean = false, var size: Int = 0){
    fun add(s: String, a: Int = 0){
        if (s.length > a && s.isNotEmpty()){
            val index = s[a] - '0'
            if (childs[index] == null)
                childs[index] = MishaNode(s[a])
            childs[index]!!.add(s, a + 1)
        } else {
            size = a
            flag = true
        }
    }

    fun find(s: String, a: Int = size): Boolean {
        if (s.length == a)
            return flag
        val index = s[a] - '0'
        return childs[index]?.find(s, a + 1) ?: run { return false }
    }

    fun start(s: String, a: Int = 0): MishaNode? {
        if (s.length == a + 1) {
            this.size = a
            return this
        }
        val index = s[a] - '0'
        return childs[index]?.start(s, a + 1) ?: run { return null }
    }
}


fun main(args: Array<String>) {

    var number = BigInteger.ONE
    for (i in 0..800){
        TREE.add(number.toString())
        number = number.shiftLeft(1)
    }

    val scan = System.`in`.bufferedReader()

    val t = scan.readLine().trim().toInt()

    for (tItr in 1..t) {
        val a = scan.readLine()

        val result = twoTwo(a)

        println(result)
    }
}