times-pal-1

A palindrome is a string that is the same whether it is read from left to right or from right to left. Chota Bheem likes palindromes a lot. As a birthday gift he received two strings A and B. Now he is curious if there is a way to insert string B into string A so that the resulting string is a palindrome. You agreed to help him and even tell how many different variants of such insertions exist. Two variants are considered different if string B is inserted in different places. Print the number of possible insertion variants.

Input:-
1st line input the number of testcases and next two lines of each test case contains A and B. 

Output:- 
Print the number of variants.

SAMPLE INPUT
1
aba
b

SAMPLE OUTPUT
2

Explanation

You can insert B in 4 different places:
Before the first letter of A. The result is "baba" and it is not a
   palindrome.
After the first letter 'a'. The result is "abba" and it is a
   palindrome.
After the letter 'b'.The result is "abba" and it is also a
   palindrome.
After the second letter 'a'. The result is "abab" and it is not a
   palindrome.

So, the answer for this testcase is 2.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def pla(h):
	return h == h[::-1]
def insert(original, new, pos):
	return original[:pos] + new + original[pos:]
	
 
 
for _ in range(eval(input())):
	s = input()
	m = input()
	count = 0
	for i in range(0, len(s)+1):
		k = insert(s, m, i)
		if pla(k):
			count  += 1
	print(count)


for  i in range(eval(input())):
	a ,b = input(), input()
	ans = 0 
	for j in range(len(a)+1):
		chk  = a[:j] + b + a[j:]
		if  chk == chk[::-1]:
			ans += 1
	print(ans)
	


t=eval(input())
for k in range(0,t):
	s=input()
	r=input()
	c=0
	for i in range(0,len(s)):
		a=''
		for j in range(0,i):
			a=a+s[j]
		a=a+r
		for j in range(i,len(s)):
			a=a+s[j]
		b=a[::-1]
		if b==a:
			c=c+1
	a=s+r
	b=a[::-1]
	if a==b:
		c=c+1
	print(c)


t = int(eval(input()))
while(t>0):
	a = input()
	b = input()
	c = 0
	for i in range(0,len(a)+1):
		k=a
		k = k[:i] + b + k[i:]
		if(k==k[::-1]):
			c+=1
		else:
			continue
	print(c)
	t-=1
			


__author__ = 'lavee_singh'

from collections import MutableString
def solve(a, b):
	count = 0
	for i in range(len(a)+1):
		c = MutableString(a)
		c.insert(i, b)
		if c == c[::-1]: count += 1
	return count

for _ in range(eval(input())):
	a = MutableString(input())
	b = MutableString(input())
	print(solve(a, b))


def rev(strin):
	s=strin[::-1]
	if s==strin:
		return 1
	else:
		return 0
n=eval(input())
for i in range(n):
	su=0
	a=input()
	b=input()
	l=len(a)
	for j in range(l+1):
		m=a[:j]+b+a[j:]
		k=rev(m)
		if k==1:
			su+=1
	print(su)


for  i in range(eval(input())):
	a ,b = input(), input()
	count = 0 
	for j in range(len(a)+1):
		x  = a[:j] + b + a[j:]
		if  x == x[::-1]:
			count+= 1
	print(count)
	


def pla(h):
	return h == h[::-1]
def insert(original, new, pos):
	return original[:pos] + new + original[pos:]
	
 
 
for _ in range(eval(input())):
	s = input()
	m = input()
	count = 0
	for i in range(0, len(s)+1):
		k = insert(s, m, i)
		if pla(k):
			count  += 1
	print(count)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t = int(input());

while ( t ):
	a= input();
	b= input();

	c = 0;
	
	s= a+b;

	if ( s == s[::-1] ):
		c+=1;
	for i in range (0,len(a))	:
		s = a[0:i]+b+a[i:];
		if ( s == s[::-1] ):
			c+=1;
	print(c);
	t-=1;



def pla(h):
	return h == h[::-1]
def insert(original, new, pos):
	return original[:pos] + new + original[pos:]
	


for _ in range(eval(input())):
	s = input()
	m = input()
	count = 0
	for i in range(0, len(s)+1):
		k = insert(s, m, i)
		if pla(k):
			count  += 1
        print(count)


for x in range(int(input())):
	a = input()
	b = input()
	count = 0
	for y in range(len(a) + 1):
		f = a[:y] + b + a[(y):]
		count += f == f[::-1]
	print(count)


__author__ = 'Kiran Chary'
t=int(input(''))
p=0
for i in range(0,t):
	a=input('')
	b=input('')
	l=len(a)
	for k in range(0,l+1):
		r=a[0:k]+b+a[k:l]
		if r==r[::-1]:
			p=p+1
	print(p)
	p=0



'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
n = int(input())
for i in range(0,n):
	a = input()
	b = input()
	ctr = 0
	for j in range(0,len(a)+1):
		aa = a[0:j]
		bb = a[j:len(a)]
		#print "{} {}".format(aa, bb)
		cc = aa + b + bb
		if cc == cc[::-1]:
			ctr+=1
	print(ctr)
	ctr = 0


def plal(d):
	return d == d[::-1]
def dalo(purana, nya, po):
	return purana[:po] + nya + purana[po:]
	
 
 
for _ in range(eval(input())):
	p = input()
	o = input()
	f = 0
	for j in range(0, len(p)+1):
		z = dalo(p, o, j)
		if plal(z):
			f  += 1
	print(f)


def isPal(s):
	if s == s[::-1]:
		return True
	else:
		return False


t = int( input())
for i in range(t):
	a,b = input(), input()
	n = len(a)
	count = 0
	for j in range(0,n+1):
		w = a[:j] + b + a[j:]
		if isPal(w):
			count = count + 1
	print(count)


"""
A palindrome is a string that is the same whether it is read from left to right or from right to left. Chota Bheem likes palindromes a lot. As a birthday gift he received two strings A and B. Now he is curious if there is a way to insert string B into string A so that the resulting string is a palindrome. You agreed to help him and even tell how many different variants of such insertions exist. Two variants are considered different if string B is inserted in different places. Print the number of possible insertion variants.

Input:-
1st line input the number of testcases and next two lines of each test case contains A and B.
"""



def gotoThisfunc():
	T = int(input(''))
	for i in range(T):
		A = input('')
		B = input('')
		N = len(A) + 1
		num = 0
		for i in range(N):
			if (i == 0 ):
				newString = B + A
				if (newString[::-1] == newString):
					num = num + 1
			elif ( i == N-1):
				newString = A + B
			   	if (newString[::-1] == newString):
					num = num + 1
			else:
				newString = A[0:i] + B + A[i:]
				if (newString[::-1] == newString):
					num = num + 1
		print(num)


if __name__ == "__main__":
	gotoThisfunc();



def pla(h):
	return h == h[::-1]
def insert(original, new, pos):
	return original[:pos] + new + original[pos:]
	
 
 
for _ in range(eval(input())):
	s = input()
	m = input()
	count = 0
	for i in range(0, len(s)+1):
		k = insert(s, m, i)
		if pla(k):
			count  += 1
	print(count)


def pla(h):
	return h == h[::-1]
def insert(original, new, pos):
	return original[:pos] + new + original[pos:]
	
 
 
for _ in range(eval(input())):
	s = input()
	m = input()
	count = 0
	for i in range(0, len(s)+1):
		k = insert(s, m, i)
		if pla(k):
			count  += 1
	print(count)