Description

一天Rose同學(xué)想得到一個僅由01組成的字符串S，Jack同學(xué)為了讓Rose同學(xué)開心，于是打算去商店購買另一個也僅由01組成的字符串T。而商店的字符串價格由它的長度決定，比如字符串011售價3元，001011售價6元，商店可以提供任意的字符串。

心靈手巧的Jack為了省錢，決定低價購入一個較短的字符串并對其進(jìn)行改造，改造不需要花錢，但只能進(jìn)行兩個操作：對字符串T的首部加上一個0，同時對其尾部加上一個1；或者對字符串T的首部加上一個1，同時對其尾部加上一個0。比如字符串T為010010，Jack可以將它改造為10100100或者00100101。

現(xiàn)在Rose已經(jīng)給出了字符串S，請問Jack最少需要購買多少長度的字符串，使得心靈手巧的他可以把從商店購買來的字符串轉(zhuǎn)化成字符串S呢？

Input

多組輸入，第一行數(shù)字t(1≤t≤100)代表共有t組數(shù)據(jù)。

每組數(shù)據(jù)僅一行S，代表Rose期望的字符串，字符串僅包含0和1，長度不超過10^3。

Output

對于每組輸入，每行請輸出一個數(shù)字，代表Jack需要購買的最短字符串長度。

Sample Input

3
101010
11
01101

Sample Output

0
2
1

HINT

對于第一組樣例，Jack可以不購買任何字符串，僅憑他的兩種操作就可以拼出Rose所需要的字符串S。

解析：其實我們可以反著想，然后把給定的兩端不斷拆，直到不能拆(兩端同為0或者1)，那么此時串的長度就是我們需要購買的長度。

#include <stdio.h>
#include <string.h>
char a[1005];
int main()
{int t,l,x,y;scanf("%d",&t);while(t--){scanf("%s",a);l=strlen(a);//字符串長度x=0,y=l-1;//左端點，右端點while(x<y&&a[x]!=a[y]) x++,y--;//兩端不同，可以拆，注意x<y條件printf("%d\n",y-x+1);//答案長度}return 0;
}