# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## Again LCS

You are given two permutations of the numbers from **1-N** called **P _{1}** and

**P**. You are also given two integers

_{2}**C**and

_{1}**C**Let

_{2}.**S**be a sequence formed by concatenating

_{1}**P**times. Also let

_{1}C_{1}**S**be a sequence formed by concatenating

_{2}**P**times. Your task is very simple, find the longest common sub-sequence of

_{2}C_{2}**S**and

_{1}**S**.

_{2}### Input

The first line contains an integer **T (1 ≤ T ≤ 15)**, denoting the number of test cases. Each test case consists of **4** lines. The first line contains an integer **N (1 ≤ N ≤ 50,000)**. The second line contains the permutation **P _{1}** separated by a single space. The third line contains the permutation

**P**separated by a single space. The fourth line contains two space separated integers

_{2}**C**and

_{1}(1 ≤ C_{1}≤ 5)**C**.

_{2}(1 ≤ C_{2}≤ 5)### Output

For each test case, output the case number followed by the longest common sub-sequence as required. Please check the sample i/o for more clarity of the exact format.

### Samples

Input | Output |
---|---|

4 3 1 2 3 2 1 3 1 2 3 1 2 3 2 1 3 2 2 7 3 1 7 6 5 2 4 1 2 3 7 6 5 4 3 2 10 1 2 3 4 5 6 7 8 9 10 10 9 8 7 6 5 4 3 2 1 5 3 | Case 1: 3 Case 2: 4 Case 3: 12 Case 4: 7 |

#### sgtlaugh

→

Login to submit