B. Broken String
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a string $$$s$$$ consisting of $$$n$$$ digits.

You can do the following operation as many times as you want:

Choose one digit and increase it by $$$1$$$ (if it isn't $$$9$$$) or decrease it by $$$1$$$ (if it isn't $$$0$$$).

You have to make the string palindrome (i.e. $$$s[i] = s[n-i+1]$$$ for every $$$i$$$: $$$1 \le i \le n$$$) using the minimum number of operations.

Input

The first line contains an integer $$$t$$$ $$$(1 \le t \le 10^{3})$$$ , the number of testcases.

Every testcase consists of one string $$$s$$$ $$$(1 \le |s| \le 10^{3})$$$.

It's guaranteed that the sum of $$$|s|$$$ over all testcases doesn't exceed $$$10^3$$$.

Output

For every test case, you have to print the minimum number of operations needed to make the string palindrome.

Example
Input
3
123456789
2222
89478345
Output
20
0
10