297 - Quadtrees

四元樹(quadtree)可被用來當作圖像編碼的一種格式，背後的原理是基於任何一張圖片都可被切割成4等份，被分割後的每一塊又可再分割成4等份，如此不斷分割下去。每一張圖可被視為樹的父節點，而被分割的四個區塊則以其四個子節點表示，其次序是預先定義的。

如果整張圖只有一種顏色，則可以用只有一個節點的四元樹來表示。一般而言，當一個區塊內有多種顏色才需要再作細部的切割，所以這種四元樹各節點的深度不一定會相同。

本題要處理的是圖片大小為32x32的黑白圖片，共有1024個像素(pixel)，並且要把兩張圖"加"起來組合成新的圖片，"加"的動作是指一個像素在原來的兩張圖上最少有一張是黑色，則該像素為黑色，否則該像素為白色。

本題會給你兩張圖的四元樹表示式，你必須寫一個程式計算這兩張圖相加之後，所有黑色像素的總數。

下圖顯示圖片分割的順序，並以一個例子表示兩張圖片相加所產生的新圖片，及其四元樹的表示方式。

Input Specification

程式一開始會有一個整數N表示測試資料的總數。

每組測試資料有兩列字串，每個字串表示一張圖，以"前序"的方式來表示一個四元樹，'p'代表父節點，'f'(full)代表黑色的區塊，'e'(empty)表示白色的區塊。字串保證是正確的四元樹格式，且樹的深度不會超過5。

Output Specification

請輸出每組測試資料的合成圖有幾個像素是黑色的，輸出格式："There are X black pixels." X表示黑像素的總數。

Example Input

3
ppeeefpffeefe
pefepeefe
peeef
peefe
peeef
peepefefe

Example Output

There are 640 black pixels.
There are 512 black pixels.
There are 384 black pixels.

原文出處