//... copyright @ASHISH JHA ... _/\_******
/*Licensed under the "THE BEER-WARE LICENSE" (Revision 42):
Ashish_Jha wrote this file. As long as you retain this notice you
can do whatever you want with this stuff. If we meet some day, and you think
this stuff is worth it, you can buy me a beer or coffee in return
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define MOD 1000000007
#define pb push_back
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define INF 1e10+1
const ll siz = 150005;
bool flg=true;
ll check(string str,ll st,ll end)
{
set<char> s;
ll flg=0;
for(ll i=st;i<=end;++i)
{
s.insert(str[i]);
}
if(s.size()==1)
return 1;
else
return 2;
}
ll rec(string str,ll low,ll high)
{
if(low==high)
return 0;
ll ele;
if(check(str,low,high)==1)
ele=1;
else
ele=0;
ll mid=(low+high)/2;
if((low-high)%2==0)
{
if(ele==1)
return 0;
else
{
return INF;
}
}
else
{
if(ele==1)
return 0;
else
return (1+min(rec(str,low,mid),rec(str,mid+1,high)));
}
}
ll re=1e5+1;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
//cout<<check("baaa",0,3)<<endl;
ll t;
cin>>t;
while(t--)
{
flg=true;
string str;
cin>>str;
ll ans=rec(str,0,str.size()-1);
if(ans>re)
cout<<"-1"<<endl;
else
cout<<ans<<endl;
}
return 0;
}
ICAgIC8vLi4uIGNvcHlyaWdodCBAQVNISVNIIEpIQSAuLi4gXy9cXyoqKioqKgovKkxpY2Vuc2VkIHVuZGVyIHRoZSAiVEhFIEJFRVItV0FSRSBMSUNFTlNFIiAoUmV2aXNpb24gNDIpOgogIEFzaGlzaF9KaGEgd3JvdGUgdGhpcyBmaWxlLiBBcyBsb25nIGFzIHlvdSByZXRhaW4gdGhpcyBub3RpY2UgeW91CiAgY2FuIGRvIHdoYXRldmVyIHlvdSB3YW50IHdpdGggdGhpcyBzdHVmZi4gSWYgd2UgbWVldCBzb21lIGRheSwgYW5kIHlvdSB0aGluawogIHRoaXMgc3R1ZmYgaXMgd29ydGggaXQsIHlvdSBjYW4gYnV5IG1lIGEgYmVlciBvciBjb2ZmZWUgaW4gcmV0dXJuCiovCiAgICAjaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgogICAgdXNpbmcgbmFtZXNwYWNlIHN0ZDsKICAgIHR5cGVkZWYgbG9uZyBsb25nIGludCBsbDsKICAgICNkZWZpbmUgTU9EIDEwMDAwMDAwMDcKICAgICNkZWZpbmUgcGIgcHVzaF9iYWNrCiAgICAjZGVmaW5lIHBpIHBhaXI8bGwsbGw+CiAgICAjZGVmaW5lIHBpaSBwYWlyPGxsLHBhaXI8bGwsbGw+PgogICAgI2RlZmluZSBJTkYgMWUxMCsxCiAgICBjb25zdCBsbCBzaXogPSAxNTAwMDU7CiAgICBib29sIGZsZz10cnVlOwogICAgbGwgY2hlY2soc3RyaW5nIHN0cixsbCBzdCxsbCBlbmQpCiAgICB7CiAgICAgICAgc2V0PGNoYXI+IHM7CiAgICAgICAgbGwgZmxnPTA7CiAgICAgICAgZm9yKGxsIGk9c3Q7aTw9ZW5kOysraSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHMuaW5zZXJ0KHN0cltpXSk7CiAgICAgICAgICAgIH0KICAgICAgICBpZihzLnNpemUoKT09MSkKICAgICAgICAgICAgcmV0dXJuIDE7CiAgICAgICAgZWxzZQogICAgICAgICAgICByZXR1cm4gMjsKICAgIH0KICAgICAKICAgIGxsIHJlYyhzdHJpbmcgc3RyLGxsIGxvdyxsbCBoaWdoKQogICAgewogICAgICAgIGlmKGxvdz09aGlnaCkKICAgICAgICAgICAgcmV0dXJuIDA7CiAgICAgICAgbGwgZWxlOwogICAgICAgIGlmKGNoZWNrKHN0cixsb3csaGlnaCk9PTEpCiAgICAgICAgICAgIGVsZT0xOwogICAgICAgIGVsc2UKICAgICAgICAgICAgZWxlPTA7CiAgICAgICAgbGwgbWlkPShsb3craGlnaCkvMjsKICAgICAgICBpZigobG93LWhpZ2gpJTI9PTApCiAgICAgICAgewogICAgICAgICAgICBpZihlbGU9PTEpCiAgICAgICAgICAgICAgICByZXR1cm4gMDsKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHJldHVybiBJTkY7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIGlmKGVsZT09MSkKICAgICAgICAgICAgICAgIHJldHVybiAwOwogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICByZXR1cm4gKDErbWluKHJlYyhzdHIsbG93LG1pZCkscmVjKHN0cixtaWQrMSxoaWdoKSkpOwogICAgICAgIH0KICAgIH0KICAgIGxsIHJlPTFlNSsxOwogICAgaW50IG1haW4oKSB7CiAgICAgICAgICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgICAgICAgICBjaW4udGllKE5VTEwpOwogICAgICAgICAgICBjb3V0LnRpZShOVUxMKTsKICAgICAgICAvL2NvdXQ8PGNoZWNrKCJiYWFhIiwwLDMpPDxlbmRsOwogICAgICAgICBsbCB0OwogICAgICAgICBjaW4+PnQ7CiAgICAgICAgIHdoaWxlKHQtLSkKICAgICAgICAgewogICAgICAgICAgICAgZmxnPXRydWU7CiAgICAgICAgICAgIHN0cmluZyBzdHI7CiAgICAgICAgICAgIGNpbj4+c3RyOwogICAgICAgICAgICBsbCBhbnM9cmVjKHN0ciwwLHN0ci5zaXplKCktMSk7CiAgICAgICAgICAgIGlmKGFucz5yZSkKICAgICAgICAgICAgICAgIGNvdXQ8PCItMSI8PGVuZGw7CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIGNvdXQ8PGFuczw8ZW5kbDsKICAgICAgICAgfQogICAgICAgICByZXR1cm4gMDsKICAgIH0KICAgICAKCg==