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

Submit: 923 Solved: 244

[Submit][Status][Web Board]

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

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.

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

```
1
3 5
abc
bcbab
```

```
2 ab
```