Sarfaraz Forgot his laptop's password But Somehow he got a Binary String . And He know that after Adding All the Prime Numbers less than that Strings is the password . As the string is very big so he decided to do this by an algorithm. But in end he is unable to Crack the password. So he decided to take help of his friend Deepak. If Deepak is able to Crack the password then Sarfarz will Give him a treat Of a RiceBow.
Help Deepak in Cracking the Password

Constraints
1<='t'<=10^5
1<=(length of string)<=20
string(0,1)

Input:
First line contain a single integer 't' No. of test cases
next 't' line contains a String contains different pattern of 0's and 1's

Output
print 't' lines each total sum of Prime Numbers below that binary string

Sample Input
2
110
1111

Sample Output
10
41