쿼드트리

어떤 컴퓨터 아티스트는 32 × 32 크기의 흑백 이미지를 다룬다. 한 이미지는 모두 1024개의 픽셀로 이루어진다. 이 아티스트가 하는 작업 중 하나는 두 이미지를 더해서 새 이미지를 만드는 것이다. 더한 결과 이미지에서 어떤 픽셀은 두 원본 이미지 중 적어도 하나에서 검은색이었다면 검은색이 되고, 그렇지 않으면 흰색이 된다.

쿼드트리(quadtree)는 이런 이미지를 부호화하는 표현 방식이다. 핵심 아이디어는 어떤 이미지든 네 개의 사분면으로 나눌 수 있고, 각 사분면을 다시 네 개의 하위 사분면으로 나눌 수 있으며, 이를 반복할 수 있다는 것이다. 쿼드트리에서 전체 이미지는 부모 노드가 되고, 네 사분면은 아래에 표시된 정해진 순서대로 네 개의 자식 노드가 된다.

전체 이미지(또는 어떤 사분면)가 한 가지 색이면 하나의 노드로 표현할 수 있다. 일반적으로 사분면은 서로 다른 색의 픽셀이 섞여 있을 때에만 다시 나누면 되므로, 쿼드트리의 깊이는 균일하지 않을 수 있다.

노드가 하나뿐인 쿼드트리의 전위 순회(preorder) 표현은, 그 노드가 비어 있는(흰색) 사분면이면 e, 가득 찬(검은색) 사분면이면 f이다. 노드가 둘 이상인 쿼드트리의 전위 순회 표현은 부모를 뜻하는 문자 p 뒤에, 위에 표시된 사분면 순서대로 네 하위 트리의 전위 순회 표현을 이어 붙인 것이다.

두 이미지의 쿼드트리 표현이 주어질 때, 두 이미지를 더해서 얻은 이미지의 검은색 픽셀 개수를 구하는 프로그램을 작성하여라.

아래 그림은 첫 번째 예제를 (위에서 아래로) 이미지, 쿼드트리, 전위 순회 문자열, 픽셀 개수의 순서로 보여 준다. 사분면 번호는 그림 위쪽에 표시되어 있다.

문제

1. 아래 이미지를 부호화하는 쿼드트리의 전위 순회 표현을 구하여라.
   
2. 32 × 32 이미지를 부호화하는 쿼드트리의 전위 순회 문자열이 가질 수 있는 가장 짧은 길이와 가장 긴 길이는 각각 얼마인가? 이유를 설명하여라.
3. 아래 명세를 만족하는 프로그램을 작성하여라.

첫 번째 줄에 테스트 케이스의 수 $N$이 주어진다. 각 테스트 케이스는 두 줄로 이루어지며, 각 줄에 문자열이 하나씩 주어진다. 각 문자열은 쿼드트리의 전위 순회 표현이며, 입력의 모든 문자열은 항상 올바른 쿼드트리를 나타냄이 보장된다.

각 테스트 케이스마다 There are X black pixels. 형식으로 한 줄씩 출력한다. 여기서 X는 해당 테스트 케이스의 두 이미지를 더해서 얻은 이미지의 검은색 픽셀 개수이다.