You are given a binary string S of N bits. The bits in the string are indexed starting from 1. S[i] denotes the ith bit of S.
Let's say that a sequence i1, i2, …, iK produces a palindrome when applied to S, if the string S[i1] S[i2] … S[ik] is a palindrome.
In addition, a sequence i1, i2, …, iK is said to be exponential, if ij + 1 = p * ij 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
Input:
2
11010
101001011
Output:
9
18
Explanation:
The following sequences are counted in the answer: {1}, {2}, {3}, {4}, {5}, {1, 2}, {1, 4}, {2, 4}, {1, 2, 4}.
input:
3
10101000
001010
111
output:
15
12
5
input:
1
00000000
output:
23
input:
1
000000001
output:
24
input:
2
10100101
11111
output:
14
11
DEBUG THE CODE:
def pal(x):
a = bin(x)[2:]
for i in range(len(a)):
if a[i] != a[len(a)-1-i]:
return 0
return 1
n = int(input())
a = [0]*530100
for i in range(1, 530001):
if i & 1:
a[i] = pal(i)
for _ in range(n):
s = ['$']
s[1:] = int(input())
ans = 0
for i in range(1, len(s)):
fl = 1 ^ s[i]
c = 2
while c < len(s):
j = c
index = 1
while j < len(s):
index = (index << 1) | s[j] ^ fl
ans += a[index]
j *= c
c += 1
print(ans+len(s)-1)
Kindly provide the answer using the below link:
https://forms.gle/TCahzSGKAMCFAvrD8
Habitate