import java.util.*;

class Main {
	public static void main(String args[])
	{
		Scanner sc = new Scanner(System.in);
		int numTestSets = sc.nextInt();
		for(int i = 0; i < numTestSets; i++)
		{
			ArrayList<GraphNode> dictionary = new ArrayList<GraphNode>();
			if(!sc.hasNextLine())
			{
				break;
			}
			String line = sc.nextLine();
			while(!line.equals("*"))
			{
				GraphNode newNode = new GraphNode(line);
				for(GraphNode g : dictionary)
				{
					if (newNode.offByOne(g))
					{
						g.nodes.add(newNode);
						newNode.nodes.add(g);
					}
				};
				
				dictionary.add(newNode);
				//dictionary.add(new GraphNode(line));
				line = sc.nextLine();
			}
			/*for(GraphNode s : dictionary)
			{
				for(GraphNode g : dictionary)
				{
					if(s.offByOne(g))
					{
						s.nodes.add(g);
					}
				}
			}*/

			ArrayList<String> pairs = new ArrayList<String>();
			line = sc.nextLine();
			while(!line.equals(""))
			{
				pairs.add(line);
				if(!sc.hasNextLine())
					break;
				line = sc.nextLine();
			}
			for(String pair : pairs)
			{
				String[] tokens = pair.split(" ");
				GraphNode start = null;
				GraphNode end = null;
				for(GraphNode node : dictionary)
				{
					if(node.word.equals(tokens[0]))
					{
						start = node;
					}
					if(node.word.equals(tokens[1]))
					{
						end = node;
					}
					node.visited = false;  //Tom - node visits need reset as well after every test.
				}
				System.out.println(start.word + " " + end.word + " " + bfs(start,end));
			}
			if (i < numTestSets - 1) System.out.println(); //Tom - consecutive sets need a new line.
		}
	}
	
	static int bfs(GraphNode start, GraphNode finish)
	{
		LinkedList<GraphNode> queue = new LinkedList<GraphNode>();
		queue.add(start);
		start.visited = true;
		queue.add(null);
		int count = 0;

		//Added a notion of the last node we've visited.
		//2 null nodes in a row mean that there are no unvisited nodes that can be added.
		//This means that there is no link between the words.
		GraphNode lastnode = start;
		while(!queue.isEmpty())
		{
			GraphNode node = queue.poll();
			if(node == null)
			{
				if (lastnode == null)
				{
					//count will be 1 here because of the count++ line below.  This only gets triggered on the 2nd null
					return 0; 
				};
				count++;
				queue.add(null);  
			}
			else
			{
				//System.out.println("Checking: " + node.word);
				if(node.word.equals(finish.word))
				{
					return count;
				}
				for(GraphNode g : node.nodes)
				{
					if(!g.visited)
					{
						//System.out.println("Queuing: " + g.word);
						g.visited = true;
						queue.add(g);
					}
				}
			}
			lastnode = node;
		}
		return 0;
	}
}

class GraphNode
{
	ArrayList<GraphNode> nodes;
	String word;
	boolean visited;
	
	public GraphNode(String word)
	{
		nodes = new ArrayList<GraphNode>();
		this.word = word;
		visited = false;
	}
	
	public boolean offByOne(GraphNode other)
	{
		if(this.word.length() != other.word.length())
			return false;
		int count = 0;
		for(int i = 0; i < other.word.length(); i++)
		{
			if(this.word.charAt(i) != other.word.charAt(i))
				count++;
		}
		if (count == 1)
		{
			//System.out.println(this.word + " off by 1 " + other.word);
		}		
		return count == 1;
	}
}
