Description

I want my singing to bring happiness to everyone.

── Vivy

Vivy is a songstress AI, who put on a performance at the amusement park NiaLand in front of a small audience. Her duty is to make every happy with my singing. After she meets a cube AI, Matsumoto, who came from 100 years into the future, her centennial journey begins...

However, she's sill a songstress AI, whatever Matsumoto asks her to do, her duty never change: to make every happy with her singing. Therefore, she wants to create her own song.

After a lot of effort, she finally compose the melody of her song, but she doesn't have any idea about the lyrics. You are a copy-paste AI, and you're asked to help her fill the lyrics in.

You've searched a bunch of lyrics along with its melody. What you need to do is to copy the lyrics to the corresponding melody that Vivy creates. Can you help her?

---

You will be given two strings $s$ and $t$, the length of which is $n$ and $m$, respectively. The strings contain only lowercase letters (i.e. a-z).

You can copy any number of any substring of $s$, and you can reverse the substrings. Your task is to reconstruct string $t$ with the copied substrings of $s$.

• A substring of a string is a consecutive segmentation of a string. For example, cde is a substring of bcdefg, bde is not. And we call cde substring $[2,4]$ of string bcdefg.
• The reversed substring is a substring that been reversed. For example, edc is a reversed substring of bcdefg. And we call edc reversed substring $[4,2]$ of string bcdefg.

For simplicity, we want the number of substrings as small as possible.

---

For example, the first case:

3
xyz
6
xyzzyx

We can slice a substring $[1,3]$ of $s$ (xyz) and a reversed substring $[3,1]$ of $s$ (zyx) and reconstruct the desired string $t$, so the minimum number of substrings is $2$.

Note that although we can slice $[1,2]$, $[3,3]$, and $[3,1]$ to get the string $t$, the number of substrings is not minimum.

Input

The first line is an integer $T$, indicates $T$ testcases below.

For each testcase, there are $n,\ s,\ m,\ t$ line by line, respectively.

$1\le T\le 20$.

$n=|s|,\ m=|t|,\ 1\le n,m\le 3000$.

 

Output

For the first line of each testcase, output the minimum number of substrings.

For the next several lines, each line output the interval $l$ and $r$ of substrings, separated by space.

• $l$ and $r$ are the left and right boundaries of a substring. For usual substrings, output $l\le r$, and $l\ge r$ for reversed substrings. Please refer to sample input and output.

If there are multiple answers, you may output any of them. For example, both slices $[3,2]$, $[9,8]$, $[3,6]$, $[10,10]$ and slices $[3,1]$, $[8,8]$, $[3,6]$, $[10,10]$ are acceptable for the second testcase, you can output any of them.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss