Exponential SubPalindromes

All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese as well.
You are given a binary string S of N bits. The bits in the string are indexed starting from 1. S[i] denotes the i^{th} bit of S.
Let's say that a sequence i_{1}, i_{2}, …, i_{K}(1 ≤ K; 1 ≤ i_{1} < i_{2} < … < i_{K} ≤ N) produces a palindrome when applied to S, if the string S[i_{1}] S[i_{2}] … S[i_{k}] is a palindrome (that is, reads the same backward or forward).
In addition, a sequence i_{1}, i_{2}, …, i_{K}(1 ≤ K; 1 ≤ i_{1} < i_{2} < … < i_{K} ≤ N) is said to be exponential, if i_{j + 1} = p * i_{j} for each integer 1 ≤ j < K and for some integer p > 1. Note, that a sequence of one element is always exponential.
Your task is to count the number of exponential sequences that produce a palindrome when applied to S.
Input
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.
The only line of description for each test case contains a binary string S of N bits.
Output
For each test case, output a single line containing the number of exponential sequences that produce a palindrome.
Constraints
 1 ≤ T ≤ 10
 Subtask 1(20 points): 1 ≤ N ≤ 20
 Subtask 2(30 points): 1 ≤ N ≤ 1000
 Subtask 3(50 points): 1 ≤ N ≤ 5 × 10^{5}
Note
The first test of the first subtask is the example test. It's made for you to make sure that your solution produces the same verdict both on your machine and our server.
Time Limits
Time limit for the first and the second subtasks is 3s. Time limit for the third subtask is 6s.
Example
Input: 2 11010 101001011 Output: 9 18
Explanation of the first case in the example test
The following sequences are counted in the answer: {1}, {2}, {3}, {4}, {5}, {1, 2}, {1, 4}, {2, 4}, {1, 2, 4}.
Author:  kostya_by 
Tester:  pavel1996 
Editorial  http://discuss.codechef.com/problems/EXPALIN 
Tags  kostya_by, ltime32, palindrome, string 
Date Added:  27122015 
Time Limit:  3  6 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions