> #include<cstdio>
> #include<memory.h>
> #include<algorithm>
> using namespace std;
> #define SIZE 5000000
> 
> unsigned clear[21] = {0x0,0xFFFFFFFE,0xFFFFFFFD,0xFFFFFFFB,0xFFFFFFF7,0xFFFFFFEF,
>                   0xFFFFFFDF,0xFFFFFFBF,0xFFFFFF7F,0xFFFFFEFF,0xFFFFFDFF,
>                   0xFFFFFBFF,0xFFFFF7FF,0xFFFFEFFF,0xFFFFDFFF,0xFFFFBFFF,
>                   0xFFFF7FFF,0xFFFEFFFF,0xFFFDFFFF,0xFFFBFFFF,0xFFF7FFFF};  //清零整数某一位要用
> struct Queue{
> 	int value;
> 	int f;
> }queue[SIZE];
> int tail,len;
> int flag[1050000];
> void exch(int i,int j)                 //交换队列中的元素
> {
> 	int tv = queue[i].value;
> 	int tf = queue[i].f;
> 	queue[i].value = queue[j].value;
> 	queue[i].f = queue[j].f;
> 	queue[j].value = tv;
> 	queue[j].f = tf;
> }
> void push(int vl,int s)               //入堆操作
> {
> 	queue[++tail].value = vl;
> 	queue[tail].f = s;
> 	int k = tail;
> 	while(k > 1){
> 		if(queue[k].value < queue[k/2].value)
> 			exch(k,k/2),k /= 2;
> 		else
> 			break;
> 	}
> }
> void pop(int &vl,int &f)             //出堆操作
> {
> 	vl = queue[1].value;
> 	f = queue[1].f;
> 	queue[1].f = queue[tail].f ;
> 	queue[1].value = queue[tail--].value ;
> 	int k = 1,e;
> 	while(k*2 <= tail){
> 		e = 2*k;
> 		if(queue[e+1].value < queue[e].value && e+1 <= tail)
> 			e++;
> 		if(queue[e].value < queue[k].value)
> 			exch(k,e),k = e;
> 		else
> 			break;
> 	}
> }
> struct Op{
> 	char id[21];
> 	int val;
> }op[35];
> int nop;
> int adjust(int f,int j)                    //根据操作序列计算操作结果，用整数保存状态，所以用位运算
> {
> 	int t;
> 	for(int i = 0; i < len; i++){
> 		if(op[j].id[i] == 'N')
> 			continue;
> 		if(op[j].id[i] == 'C')
> 			f = f&clear[len-i];           //清零
> 		else{
> 			t = 1 << (len-i-1);
> 			if(op[j].id[i] == 'F')
> 				f = f^t;             //取反
> 			else 
> 				f = f|t;              //置1
> 		}
> 	}
> 	return f;
> }
> int bfs(int s,int t)           //开始广搜
> {
> 	int i;
> 	tail = 0;
> 	memset(flag,-1,sizeof(flag));  //flag记录某一状态是否出现过，出现过的话记录其出现所花费的最小费用
> 	push(0,s);
> 	flag[s] = 0;
> 	while(tail > 0){
> 		int tv,tf;             
> 		pop(tv,tf);
> 		for(i = 0; i < nop; i++){
> 			int ttv = tv + op[i].val;
> 			int ttf = adjust(tf,i);      //调整状态
> 			if(ttf == t)
> 				return ttv;
> 			if(flag[ttf] == -1 || flag[ttf] > ttv){ //如果某状态出现过，现在再次出现且花费比以前出现的大或相等，就没有必要再入队列了。
> 				flag[ttf] = ttv;
> 				push(ttv,ttf);
> 			}
> 		}
> 	}
> 	return -1;
> }
> bool cmp(const Op &a,const Op &b)
> {
> 	return a.val < b.val;
> }
> int main()
> {
> 	int T,nw,i,out[21],s,t,j;
> 	char ts[21];
> 	for(scanf("%d",&T); T; T--){
> 		scanf("%d%d%d",&len,&nop,&nw);
> 		for(i = 0; i < nop; i++)
> 			scanf("%s%d",op[i].id,&op[i].val);
> 		sort(op,op+nop,cmp);   //对各种操作按花费从小到大排一下序。
> 		for(i = 0; i < nw; i++){
> 			scanf("%s",ts);
> 			s = 0;
> 			for(j = 0; j < len; j++)
> 				s = s*2+ts[j]-'0';
> 			scanf("%s",ts);
> 			t = 0;
> 			for(j = 0; j < len; j++)
> 				t = t*2+ts[j]-'0';
> 			if(s == t)
> 				out[i] = 0;     //如果源和目标相等，则花费为0
> 			else
> 				out[i] = bfs(s,t);
> 		}
> 		if(out[0] == -1)                //以下为输出操作。
> 			printf("NP");
> 		else printf("%d",out[0]);
> 		for(i = 1; i < nw; i++)
> 			if(out[i] == -1)
> 				printf(" NP");
> 			else
> 				printf(" %d",out[i]);
> 			printf("\n");
> 	}
> 	return 0;
> }