A 4way tree is a representation format used to encode images. The fundamental idea behind the 4way tree is that any image can be split into four quadrants. Each quadrant may futher be splitted in four sub quadrants and so on. In the 4way tree, the image is represented by a parent node, while the four quadrants are represented by four child nodes, in a predetermined order.
Of course, if the whole image is a single color, it can be represented by a 4way tree consisting of a single node. In general, a quadrant needs to be subdivided only if it consists of pixels of different colors. As a result, the 4way tree need not be of uniform depth.
An artist works with these black and white images of 32x32 units, for a total of 1024 pixels per image. he performs an operation of adding two images together, thereby forming a new image. In the resulting image a pixel is black only if it was black in at least one of the component images, otherwise it is white.
The most significant property of this kind of image is the count of filled (black) pixels in the image. So, before adding two images together, he wants to find out the number of black pixels in the resulting image. Write a program that, given the 4way tree representation of two images, finds out the count of pixels that are black in the resulting image, which is the the addition of the two given images.
In the figure, the first example is shown (from top to bottom) as image, 4way tree, pre-order string (defined below) and number of pixels. The quadrant numbering is shown at the top of the figure.
The first line of input specifies the number of test cases (N) your program has to process.
The input for each test case is two strings, each string on its own line. The string is the pre-order representation of a 4way tree, in which the letter 'p' indicates a parent node, the letter 'f' (full) a black quadrant and the letter 'e' (empty) a white quadrant. It is guaranteed that each string represents a valid 4way tree, while the depth of the tree is not more than 5 (because each pixel has only one color).Assume the length of the string will not be more than 1000 characters.
For each test case, print the line 'A black pixels.', where A is the count of black pixels in the resulting image.
640 black pixels.
512 black pixels.
384 black pixels.