import java.io.BufferedInputStream;
import java.io.FileReader;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    static boolean oj = true;
    static Scanner sca = null;// Scanner 占用内存较多：消耗2390K！
    static Main a2908 = null;
    //若开1024*1024大小的byte存状态,耗1M内存,不用了，直接整数存状态
    static int[] clear= {0x0,0xFFFFFFFE,0xFFFFFFFD,0xFFFFFFFB,0xFFFFFFF7,0xFFFFFFEF,
            0xFFFFFFDF,0xFFFFFFBF,0xFFFFFF7F,0xFFFFFEFF,0xFFFFFDFF,
            0xFFFFFBFF,0xFFFFF7FF,0xFFFFEFFF,0xFFFFDFFF,0xFFFFBFFF,
            0xFFFF7FFF,0xFFFEFFFF,0xFFFDFFFF,0xFFFBFFFF,0xFFF7FFFF}; //清零整数某一位要用

    
    class Node implements Comparable<Node> 
    {
	int key;
	long cost;
	
	public Node(int v, long cos)
	{
	    key = v;
	    cost = cos; 
	}
	
	public int compareTo(Node o) {
	    if(cost > o.cost) return 1;
	    else if(cost < o.cost) return -1;
	    return 0;
	}
	
	public boolean equals(Object obj)
	{
	    if(obj instanceof Node)
	    {
		return (key==((Node)obj).key && cost==((Node)obj).cost);
	    }
	    return false;
	}
    }
    
    public static void run() {
	try {
	    sca = oj ? new Scanner(new BufferedInputStream(System.in))
		    : new Scanner(new FileReader("input2908.txt"));
	    int inputcase = sca.nextInt();

	    a2908 = new Main();
	    for (int i = 0; i < inputcase; i++) {
		int len = sca.nextInt();
		int quantumNum = sca.nextInt();
		int problem = sca.nextInt();
		char[][] ch = new char[quantumNum][len];
		int[] cost = new int[quantumNum];
		for (int j = 0; j < quantumNum; j++) {
		    ch[j] = sca.next().toCharArray();
		    cost[j] = sca.nextInt(); 
		}
				
		int[][]prob = new int[problem][2];
		for (int j = 0; j < problem; j++) {
		    prob[j][0] = Integer.parseInt(sca.next(),2);
		    prob[j][1] = Integer.parseInt(sca.next(),2);
		}
		solve(ch, cost, prob);
	    }
	    //clossAll();
	} catch (Exception e) {
	    e.printStackTrace();
	}
    }

    static void solve(char[][] quantum, int[] cost,int[][]prob) {
	for (int ip = 0; ip < prob.length; ip++) {
	    int start = prob[ip][0];
	    int end = prob[ip][1];
	    
	    //下面建立最小堆优先队列，bfs
	    PriorityQueue<Node> pq = new PriorityQueue<Node>(128);
	    //存状态，cost
	    HashMap<Integer, Long> map = new HashMap<Integer, Long>();
	    bfs(start, end, quantum, cost, pq, map);
	}//for ip
	 System.out.println();
    }//solve

    
    private static void bfs(int start,int endc,char[][] quantum, int[] cost,
	    PriorityQueue<Node> pq, HashMap<Integer, Long> map){
	   
	    if(start == endc){
		    System.out.print("0 ");
		    return;
		}
	    Node root = a2908.new Node(start,Long.valueOf(0)); 
	    pq.add(root);
	    boolean bfind = false;
	    long necost = 0;
	    int len = quantum[0].length;
	    while (!(pq.isEmpty()||bfind))
	    {
		 Node now = pq.poll();
    	        //宽度bfs搜索，使用了最小堆优先队列，搜出的就是最短路
                for (int i = 0; i < quantum.length; i++)
                {
                    int ne = doByte(len, now.key, quantum[i]);
                    necost = now.cost + cost[i];
                	if(ne == endc){
                	    bfind = true;
                	    break;
                	}
                	Long getCost = map.get(ne);
                	if (getCost == null || getCost > necost){
                 		map.put(ne, necost);
                 		Node next = a2908.new Node(ne, necost);
                 		pq.add(next);
                	}
                 }
               }//while
	    if(!bfind){
		System.out.print("NP ");
	    }
	    else
	    {
		System.out.print(necost + " ");
	    }
	    return;
    }//bfs
    
    
    //根据操作序列计算操作结果，用整数保存状态，所以用位运算
    private static int doByte(int len,int src, char[]quant){
    	int f = src;
    	int t = 0;
    	for(int i = 0; i < quant.length; i++){
    	  char q = quant[i];
	    switch(q)
	    {
	    	case 'N':
	    	    break;
	    	case 'F':
	    	    t = 1 << (len-i-1); //取反
	    	    f = f^t;    
	    	    break;  
	    	case 'C':
	    	    f = f&clear[len-i]; //清零
	    	    break;  
	    	case 'S':
	    	    t = 1 << (len-i-1);
	    	    f = f|t;            //置1
	    	    break;
	    	default:
	    	   break; 
	    }	
    	}	
    	return f;
    }
  
    /**
         * @param args
         */
    public static void main(String[] args) {
	run();

    }

}//AcmPKU2908