Minimum Appends to Make Palindrome

You are given a string s. Your task is to determine the minimum number of characters that need to be appended to the end of s in order to make it a palindrome.

A palindrome is a string that reads the same backward as forward. Mathematically, a string s is a palindrome if \[ s = s^R \] where \(s^R\) denotes the reverse of s.

For example, for the string abca, by appending 3 characters to the end, we can obtain abcaacba, which is a palindrome. Similarly, if the string is already a palindrome, then no characters are required.

inputFormat

The first line contains an integer T representing the number of test cases.

Each of the following T lines contains a single non-empty string s consisting of lowercase letters.

Constraints: \(1 \le T \le 10^5\), and the length of s is at least 1.

outputFormat

For each test case, output a single integer on a new line indicating the minimum number of characters required to append to the string so that it becomes a palindrome.

## sample

2
abca
race

3
3

</p>