As Hardik is pretty interested in problem solving . Specially he loves DYNAMIC PROGRAMMING . Hardik is given a string consisting of only 0s and 1s. The problem is to change the given string to a barcode string . In one move Hardik can change any substring of length 2 to a desired substring containing only zeros and ones. Barcode string is a string containing only zeros and ones but in an alternative manner that means ones and zeros occurs alternatively .

CONSTRAINTS

1<=t<=1000

1<=|S|<=1000

INPUT

First line of input contains one integer t denoting number of testcases. Each test case consists of two lines length of string and a string.

OUTPUT

Minimum number of moves required to change given string into a barcode string.