11491149 SUSTech Online Judge
Problem 1149 --Presuffix [Medium]

1149: Presuffix [Medium]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 923  Solved: 244
[Submit][Status][Web Board]

Description

Hong has two strings S and T, finds the longest prefix of S that is a suffix of T.

Input

The first line will be an integer T (1≤T≤50), which is the number of test cases.  

For each test data:

The first line contains two integers n and m (1≤n, m≤10^5)  meaning the length of the string S and the length of the string T, respectively.

The second line contains string s of length n, which consists only of lowercase letters.

The third line contains string t of length m, which consists only of lowercase letters.

Output

For each case, please print the length of the longest prefix of S that is a suffix of T and the corresponding prefix.

Sample Input

1
3 5
abc
bcbab

Sample Output

2 ab

HINT

Source

[Submit][Status]