LCPS
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Given two strings,now you asked to tell the length of the Longest Common Palindrome Substring (LCPS) of them.

For example:

A = "abacabaqq"

B = "ccacaqaba"

So the LCPS is "aba" or "aca", and the length is 3.

But tokitsukaze think it's too simple to ask for the length.
tokitsukaze want you to tell the smallest lexicographical order one."aba" is smaller than "aca" , so the answer is "aba".
However , the output may very large.You just need to tell the index of answer in A and B.If the answer appears multiple times in A or B , you need tell the smallest one.(the index starts from 1.)
Now the answer is "aba".In string A , substring A[1..3]="aba" and A[5..7]="aba" .In string B , substring B[7..9]="aba".So you just output"1 3" and "7 9" in one line and print a blank between them.(s[i..j]=s[i]s[i+1]...s[j])


PS: Sorry for my poor English.

输入描述:

The first line of the input contains a single integer T(T≤40), indicating the number of test cases.

In each test case:
The first line of the input contains a single integer n(1≤n≤5*10^5), indicating the length of the string A and string B. (The length of A and B is equal)
The second line of the input contains a single string A(only contains 'a'-'z').
The third line of the input contains a single string B(only contains 'a'-'z').
It's guaranteed that the sum of n in all test cases will not exceed 2*10^6.

输出描述:

The first line of the output contains a single integer ,the length of the LCPS.
The second line of the output contains two integers L1 and R1,it means that in string A , substring A[L1..R1] is the answer.
The third line of the output contains two integers L2 and R2,it means that in string B , substring B[L2..R2] is the answer.
If A and B don't have LCPS , the answer is 0,and you don't need to print L1,R1,L2,R2.
示例1

输入

复制 
2
9
abacabadd
ccacadaba
3
aaa
zzz

输出

复制 
3
1 3
7 9
0