297 - Quadtrees*****

/*
	解题要有恒心。。。。
	不错的一道题，当时没有解出。*****
	这道题主要步骤：
	*创建一颗四叉树
	*合并
	*历编
	不可盲目去寻找错误，选一测试案例，自己认真走一遍试试
*/
#include <iostream>
#include <cstdio>
#include <string>
#include <cstdlib>
using namespace std;
struct Node
{
	char ch;
	Node *fir,*sec,*thi,*fou;
};
string a;
int sum;

Node *creat(int &loc)
{
	/*
	创建树的步骤：
	步骤1：分配内存
	步骤2：递归调用
	*/
	Node *r=(Node *)malloc(sizeof(Node));
	if(loc<a.size())
	{
		
		r->ch=a[loc];
		if(a[loc]=='p')
		{
			r->fir=creat(++loc);
			r->sec=creat(++loc);
			r->thi=creat(++loc);
			r->fou=creat(++loc);
		}
		else
			r->fir=r->sec=r->thi=r->fou=NULL;
		
	}
	return r;
}

Node *combine(Node *root1,Node *root2)
{
	Node *r=(Node *)malloc(sizeof(Node));
	if(root1->ch=='f' || root2->ch=='f')
	{
		r->ch='f';
		r->fir=r->sec=r->thi=r->fou=NULL;
	}
	else if(root1->ch=='e' && root2->ch=='e')
	{
		r->ch='e';
		r->fir=r->sec=r->thi=r->fou=NULL;
	}
	else
	{
		r->ch='p';
		if(root1->ch=='p' && root2->ch=='p')
		{
			r->fir=combine(root1->fir,root2->fir);
			r->sec=combine(root1->sec,root2->sec);
			r->thi=combine(root1->thi,root2->thi);
			r->fou=combine(root1->fou,root2->fou);
		}
		else if(root1->ch=='p' && root2->ch=='e')
		{
			r->fir=root1->fir;
			r->sec=root1->sec;
			r->thi=root1->thi;
			r->fou=root1->fou;
		}
		else 
		{
			r->fir=root2->fir;
			r->sec=root2->sec;
			r->thi=root2->thi;
			r->fou=root2->fou;
		}
	}
	return r;
}

void cacluate(Node *root,int len)
{
	/*
	if(root->ch=='p')
	{
		len=len/4;
		cacluate(root->fir,len);
		cacluate(root->sec,len);
		cacluate(root->thi,len);
		cacluate(root->fou,len);
	}
	else if(root->ch=='f')
		sum+=len;
	*/
	if(root!=NULL)
	{
		if(root->ch=='f')
			sum+=len;
		len=len/4;
		cacluate(root->fir,len);
		cacluate(root->sec,len);
		cacluate(root->thi,len);
		cacluate(root->fou,len);
	}
}

int main()
{
	//freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);
	int T;
	cin>>T;
	while(T--)
	{
		int loc;
		loc=0;
		cin>>a;
		Node *root1=creat(loc);
		cin>>a;
		loc=0;
		Node *root2=creat(loc);
		Node *root=combine(root1,root2);
		sum=0;
		cacluate(root,1024);
		printf("There are %d black pixels.\n",sum);
	}
	return 0;
}