**PLEASE SOMEONE HELP ME INORDER TO SOLVE THIS**

Nth Shortest Super Sequence

Time out : 4 Sec

Memory Limit : 64MB

A shortest common supersequence of two strings is defined as the shortest possible string containing both strings as subsequences

(See Notes below for a rigorous definition of a supersequence). There can be more than one shortest supersequence for two strings.

For example the strings “ABC” and “ACB” have “ABCB” and “ACBC” as shortest supersequences (both have a length

of 4 characters and contain both the strings as subsequence). Now if you sort them lexicographically

then “ABCB” comes before “ACBC”.

Given two strings S1 and S2 and a number n, your task is to find the nth shortest supersequence of these two strings (1 based index).

Input Format:

The first line contains one integer t, the number of testcases. (1 <= t <= 200)

This will be followed by t test cases, each containing 3 lines.

- The first line of each test case gives the first string S1
- The second line gives the second string S2
- The third line will give the number n (1 based index)

Constraints:

- The Strings S1 and S2 will contain only uppercase and lowercase english letters only.
- Length of the strings S1 and S2 will be between 1 and 1000.
- n will fit into a 32 bit signed integer.

Output Format:

For each test case print the nth shortest supersequence on a separate line. If the total number of shortest supersequences is less than n then print “NO ANSWER” (without quotes).

Sample Input:

3

ABC

ACB

2

ABC

ACB

3

AAA

aaa

20

Sample Output:

ACBC

NO ANSWER

aaaAAA

Notes:

- In lexicographical ordering, uppercase letters come before lowercase letters (The order - from low to high - is A to Z followed by a to z).
- Consider two strings A and B of length n and m respectively. We can denote the ith character of

the strings by A[i] or B[i] respectively.Now consider S be the supersequence of A and B. Then we should be able to

list n indices X1to Xn such that the indices are in strictly increasing order

(X123…n) and S[Xi] = A[i] for all i from 1 to n. Similarly we should be able to list m indices Y1to Ym such that the indices are in strictly increasing order(Y123…m) and S[Yi] = B[i]

for all i from 1 to m. A shortest supersequence is a supersequence of minimum length.