32 lines
675 B
Python
32 lines
675 B
Python
|
m = 15546404183
|
||
|
|
|
||
|
|
def main():
|
||
|
|
n = int(input())
|
||
|
|
s = input()
|
||
|
|
|
||
|
|
left_rolling_hash = 0
|
||
|
|
right_rolling_hash = 0
|
||
|
|
pw = 1
|
||
|
|
|
||
|
|
def roll_left(h, l):
|
||
|
|
return (h*37+l)%m
|
||
|
|
|
||
|
|
def roll_right(h, l, pw):
|
||
|
|
rs = (h+l*pw)%m
|
||
|
|
pw = (pw*37)%m
|
||
|
|
return rs, pw
|
||
|
|
|
||
|
|
total = 0
|
||
|
|
for i in range(n-1):
|
||
|
|
left_rolling_hash = roll_left(left_rolling_hash, ord(s[i]))
|
||
|
|
right_rolling_hash, pw = roll_right(right_rolling_hash, ord(s[-1-i]), pw)
|
||
|
|
if left_rolling_hash == right_rolling_hash:
|
||
|
|
total += 1
|
||
|
|
|
||
|
|
# print(left_rolling_hash, right_rolling_hash)
|
||
|
|
|
||
|
|
return total
|
||
|
|
|
||
|
|
|
||
|
|
for _ in range(int(input())):
|
||
|
|
print(main())
|