Word Break II

def word_break(s, word_dict):
    word_set = set(word_dict)
    memo = {}

    def dfs(start):
        if start == len(s):
            return [""]  # one valid way: empty string
        if start in memo:
            return memo[start]

        sentences = []
        for end in range(start + 1, len(s) + 1):
            word = s[start:end]
            if word in word_set:
                for sub in dfs(end):
                    if sub:
                        sentences.append(word + " " + sub)
                    else:
                        sentences.append(word)
        memo[start] = sentences
        return sentences

    return dfs(0)


# Read input
t = int(input().strip())
for _ in range(t):
    n = int(input().strip())
    dictionary = input().strip().split()
    s = input().strip()

    results = word_break(s, dictionary)
    for sentence in results:
        print(sentence)