/*******************************************
Problem - Selbat H. Turt
Solution By - Nathan Scott
*******************************************/

#include <string>
#include <iostream>
#include <vector>
#include "math.h"
using namespace std;

#define SIZE 11

struct BitVector {
	int size;
	bool bits[SIZE];

	BitVector(int s) {
		size = s;
		for (int i = 0; i < s; i++) bits[i] = false;
	}
	~BitVector() {}

	void setAsInt(int num) {
		for (int i = 0; i < size; i++) {
			if (num & 1) bits[i] = true;
			else bits[i] = false;
			num >>= 1;
		}
	}
	string toString() {
		string result = "";
		for (int i = size - 1; i >= 0; i--) {
			if (bits[i]) result += "1";
			else result += "0";
		}
		return result;
	}
};

struct Gate {
	vector<int> controls;
	int targetA;
	int targetB;
	bool isFredkin;

	Gate() {}
	Gate(string desc) {
		if (desc[0] == 'F') isFredkin = true;
		else isFredkin = false;

		int index = 2;
		while (index < (int)desc.length() && desc[index] != ',') {
			controls.push_back(desc[index] - 'a');
			index++;
		}
		index++;
		targetA = desc[index] - 'a';	
		if (isFredkin) targetB = desc[index+1] - 'a';
	}
	~Gate() {}

	void apply(BitVector & bv) {
		bool applyMe = true;
		
		for (int i = 0; i < (int)controls.size(); i++) {
			if (controls[i] >= bv.size || !bv.bits[controls[i]]) {
				applyMe = false;
				break;
			}
		}
		if (applyMe) {
			if (isFredkin) {
				if (targetA < bv.size && targetB < bv.size) {
					bool temp = bv.bits[targetA];
					bv.bits[targetA] = bv.bits[targetB];
					bv.bits[targetB] = temp;
				}
			}
			else {
				if (targetA < bv.size) bv.bits[targetA] = !bv.bits[targetA];
			}
		}
	}
};

string readGate(istream & cin) {
	string result = "";
	while (cin.peek() != 'T' && cin.peek() != 'F') cin.get();
	result += cin.get();
	result += cin.get();
	while (cin.peek() != ')' && !cin.eof() && cin.peek() != -1) {
		result += cin.get();
	}
	result += cin.get();
	return result;
}

int main() {
	int N;
	cin >> N;

	vector<Gate> circuit;
	for (int i = 0; i < N; i++) {
		int size, gates;
		int j;
		cin >> size >> gates;
		for (j = 0; j < gates; j++) {
			string s = readGate(cin);
			circuit.push_back(Gate(s));
		}
		
		char c;
		if (i) cout << endl;
		cout << "Circuit #" << i+1 << ":" << endl;
		for (c = ('a' + size-1); c >= 'a'; c--) cout << c;
		cout << "    ";
		for (c = ('a' + size-1); c >= 'a'; c--) cout << c;
		cout << endl;
		for (j = 0; j < size; j++) cout << '-';
		cout << "    ";
		for (j = 0; j < size; j++) cout << '-';
		cout << endl;
		
		int limit = (int)(pow(2.0, (double)size));
		BitVector bv(size);
		for (j = 0; j < limit; j++) {
			bv.setAsInt(j);
			cout << bv.toString() << "    ";
			for (int k = 0; k < (int)circuit.size(); k++) {
				circuit[k].apply(bv);
			}
			cout << bv.toString() << endl;
		}
		circuit.clear();
	}

	return 0;
}