Slogan

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Slogan
{
    class Program
    {
        static int n;
        static string[] words;
        static string slogan;
        static StringBuilder resultSb = new StringBuilder();
        static StringBuilder tempSb = new StringBuilder();
        static void Main()
        {
            n = int.Parse(Console.ReadLine());
            for (int i = 0; i < n; i++)
            {
                words = Console.ReadLine().Split();
                slogan = Console.ReadLine();
                string currentResult = slogan;
                foreach (string word in words)
                {
                    int timesMet = 0;
                    if (currentResult.StartsWith(word))
                    {
                        timesMet++;
                    }
                    if (currentResult.EndsWith(word) && currentResult.Length > word.Length)
                    {
                        timesMet++;
                    }
                    string[] splitResult = currentResult.Split(new string[] { word }, StringSplitOptions.RemoveEmptyEntries);
                    if (splitResult.Length > 1)
                    {
                        timesMet += splitResult.Length - 1;
                    }
                    currentResult = string.Join("", splitResult);
                    if (timesMet > 0)
                    {
                        tempSb.Append(String.Join(" ", Enumerable.Repeat(word, timesMet)));
                        tempSb.Append(' ');
                    }
                }
                if (currentResult.Length > 0)
                {
                    resultSb.AppendLine("NOT VALID");
                }
                else
                {
                    while (slogan != string.Empty)
                    {
                        foreach (var word in words)
                        {
                            if (slogan.StartsWith(word))
                            {
                                resultSb.Append($"{word} ");
                                slogan = slogan.Substring(word.Length);

                                if (slogan == string.Empty)
                                {
                                    resultSb.AppendLine();
                                    break;
                                }
                            }
                        }
                    }
                }
                tempSb.Clear();
            }
            Console.WriteLine(resultSb.ToString().TrimEnd());
        }
    }
}