package com.interview.graph;

import sun.misc.Queue;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;

/**
 * Created by mainuddin on 12/8/2016.
 */
public class Doublets {
    static Set<String> dictionary = new HashSet<String>();
    public static Stack<String> solve(String start, String end) {
        HashSet<String> V = new HashSet<String>();
        node s = new node();
        s.c = start;
        s.parent = null;
        V.add(start);
        Queue<node> Q = new Queue<>();
        Q.enqueue(s);
        Stack<String> res = null;
        while (!Q.isEmpty()) {
            node cur = null;
            try {
                cur = Q.dequeue();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            if (cur.c.equals(end)) {
                res = new Stack<String>();
                while (cur != null) {
                    res.push(cur.c);
                    cur = cur.parent;
                    }
                return res;
                } else {
                char[] S = cur.c.toCharArray();
                char[] ref = cur.c.toCharArray();
                for (int i = 0; i < S.length; i++) {
                    for (int j = 0; j < 26; j++) {
                        S[i] = (char) (j + 'a');
                        String h = new String(S);
                        if (S[i] != ref[i] && !V.contains(h) && dictionary.contains(h)) {
                            V.add(h);
                            node n = new node();
                            n.c = h;
                            n.parent = cur;
                            Q.enqueue(n);
                            }
                        }
                    S[i] = ref[i];
                    }
                }
            }
        return res;
        }
    static class node {
        String c;
        node parent;
    }
    public static void main(String[] args) {

        Scanner file = null;
        try {
            file = new Scanner(new File("E:\\L2-T2\\interview-master\\src\\com\\interview\\graph\\dictionary.txt"));
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
       // int counter = 0;
        while (file.hasNext()) {
            dictionary.add(file.next().trim().toLowerCase());
         //   counter++;
        }
        Scanner in = new Scanner(System.in);
        int test_cases = 0;
        String s1 = new String();
        String s2 = new String();
        test_cases = in.nextInt();
        //System.out.println(counter+","+recounter);
        while(true) {
            Scanner str = new Scanner(System.in);
            s1 = str.nextLine().toLowerCase();

            s2 = str.nextLine().toLowerCase();
            Stack<String> sol = solve(s1, s2);
            if (sol != null) {
                while (!sol.isEmpty()) {
                    System.out.print(sol.pop()+"->");
                }
                System.out.println();
            } else if (sol == null || sol.isEmpty()) {
                System.out.println("No solution.");
            }
            test_cases--;
            if (test_cases == 0) break;
        }
    }
}