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())