There is college whose name will not be disclosed. To raise the level the college management installed wifi connections. There was poor hostel where there was a poor floor. The floor had n rooms. Three routers were setup just for that floor to increase the signal strength. Still there they weren't able to operate the internet. Also no router can hold more than the current connections from that wing. They finally found that if three adjacent room connects to a same router then there won't be an internet connection established. You know which room is connected to which router. Since they are very lazy (as it is the typical character of their college) they want to swap the router connection between certain room so that the number of unswapped rooms are maximum and also no three continuous rooms are connected to the same wifi router.

Input

First line T denoting the number of cases (T ≤ 40)

For each line a string x is given which determines which denotes which room is connected to which router (size of x ≤ 50)

Output

Output the maximum unswapped rooms which follows the above mentioned condition or output -1 if it is not possible to make a valid arrangement

Example

Input:
2
111222333
11111111322

Output:
6
7