You are given a string s and a word list w which is a list of unique strings. Break the string into a sequence of words where each word is an element in w.

Examples

s: "workattech"
w: ["tech", "work", "problem", "at", "workattech"]
Result: ["work at tech", "workattech"]

s: "roundandround"
w: ["and", "round", "roundand"]
Result: ["round and round", "roundand round"]

Note:

• The resultant list should be lexicographically sorted. Consider that ' ' is smaller than 'a'.
• The strings contain lowercase English alphabets only.

Testing

Input Format

The first line contains an integer ‘T’, denoting the number of test cases.

For each test case the input has three lines:

• The string s.
• An integer ‘n’ denoting the size of the word list w.
• n space-separated strings denoting the elements of the word list w.

Output Format

For each test case, the output has the following lines:

• The first line contains an integer ‘m’ denoting the total no of possible sentences.
• The next m line each contain a sentence created by breaking the string.

Sample Input

2
workattech
5
tech work problem at workattech
roundandround
3
and round roundand

Expected Output

2
work at tech
workattech
2
round and round
roundand round

Constraints

1 <= T <= 100

1 <= s length <= 50

1 <= w size <= 10

1 <= wi length <= 10