종말의 정렬

사과와 바나나는 맛있지만 위험하기도 하다. 오래된 예언에 따르면, 이들을 특정한 순서로 늘어놓으면 세상이 멸망한다고 한다. 세상에 지친 당신은 이를 시험해 보기로 한다.

처음에 사과와 바나나가 한 줄로 놓여 있다. 허용되는 연산은 한 가지뿐이다. 연속한 임의 개수의 과일을 골라, 그 과일들을 모두 한 종류(모두 사과이거나 모두 바나나)로 바꾼다. 선택한 구간의 길이는 그대로이며, 그 안의 과일이 전부 같은 종류가 된다.

당신은 되도록 적은 횟수로 멸망의 배열을 만들고 싶다. 처음 배열을 멸망의 배열로 바꾸는 데 필요한 최소 연산 횟수를 구하라.

첫째 줄에 테스트 케이스의 수 $t$ ($t \le 100$)가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄은 처음 배열, 둘째 줄은 세상을 멸망시키는 멸망의 배열이다. 두 줄은 모두 문자 A(사과)와 B(바나나)로만 이루어지고, 길이가 서로 같으며 $200$ 이하이고, 앞뒤에 공백이 없다.

각 테스트 케이스마다 멸망의 배열을 만들기 위한 최소 연산 횟수를 한 줄에 출력한다.

예를 들어 처음 배열이 BAAAB이고 멸망의 배열이 ABBAA라면, 먼저 줄 전체를 사과로 바꾸어 AAAAA를 만들고, 그다음 2번째와 3번째 과일을 바나나로 바꾸면 ABBAA가 된다. 이렇게 하면 2번의 연산이면 충분하다.