#include<vector>
#include<iostream>
#include<map>
#include<string>

int val(string s) {
  int w = 0;
  int pot = 1;
  for (int j=s.length()-1; j>=0; j--) {
    int dig=s[j] - '0';
    w += pot*dig;
    pot *= 2;
  }
  return w;
}

int findOnes(string s2, char ch) {
  string s = s2;
  for (int j=s.length()-1; j>=0; j--) {
    if (s[j] == ch)
      s[j] = '1';
    else
      s[j] = '0';
  }
  return val(s);
}

struct Op {
  string s;
  int c;
  int xorOp, andOp, orOp;

  Op(string s, int c) : s(s), c(c) {
    xorOp = findOnes(s, 'F');
    orOp = findOnes(s, 'S');
    andOp = ~findOnes(s, 'C');
  }
  
  int apply(int v) {
    return ((v | orOp) & andOp) ^ xorOp;
  }
};

struct Word {
  int val;
  int cost;
  Word(int val, int cost) : val(val), cost(cost) {}
  bool operator<(const Word b) const {
    return cost < b.cost;
  }
};

int len, nOp, nWords;

const int Inf = 1000000000;

int dist(vector<Op> ops, int start, int end) {
  int mx = 1 << len;
  vector<Word> words;
  for (int i=0; i<mx; i++)
    words.push_back(Word(i, (i==start ? 0 : Inf)));
  multimap<int, Word> q;
  for (int i=0; i<mx; i++)
    q.insert(make_pair(words[i].cost, words[i]));

  while (!q.empty()) {
    Word w = q.begin()->second;
    q.erase(q.begin());
    for (int i=0; i<nOp; i++) {
      int next = ops[i].apply(w.val);
      if (w.cost + ops[i].c < words[next].cost) {
        words[next].cost = w.cost + ops[i].c;
        q.insert(make_pair(words[next].cost, words[next]));
      }
    }
    if (w.val == end) return w.cost;
  }
  return -1;
}

int main() {
  int nCases;
  cin >> nCases;
  for (int caseNr=0; caseNr<nCases; caseNr++) {
    cin >> len >> nOp >> nWords;
    vector<Op> ops;
    for (int o=0; o<nOp; o++) {
      string s;
      int c;
      cin >> s >> c;
      ops.push_back(Op(s, c));
    }
    for (int i=0; i<nWords; i++) {
      string start, target;
      cin >> start >> target;
      int d = dist(ops, val(start), val(target));
      if (d == Inf)
        cout << "NP ";
      else
        cout << d << " ";
    }
    cout << endl;
  }
}