Chiến Thuật Lật Xâu

Minh và Lan đang chơi một trò chơi. Họ có hai xâu $A$ và $B$ có cùng độ dài $n$ gồm các ký tự latin viết thường. Hai người chơi lần lượt thực hiện lượt đi của mình, trong đó Minh là người đi trước.

Ở lượt của mình, Minh chọn một chỉ số $i$ từ $1$ đến $n$, chọn một trong hai xâu $A$ hoặc $B$, và chọn một ký tự latin viết thường $c$ bất kỳ, sau đó thay thế ký tự thứ $i$ trong xâu đã chọn bằng ký tự $c$.

Ở lượt của mình, Lan chọn một trong hai xâu $A$ hoặc $B$ và đảo ngược xâu đó. Nói một cách chính xác hơn, Lan thực hiện phép thay thế $A := \operatorname{rev}(A)$ hoặc $B := \operatorname{rev}(B)$, trong đó $\operatorname{rev}(P) = P_n P_{n-1} ... P_1$.

Trò chơi kéo dài cho đến khi hai xâu $A$ và $B$ bằng nhau. Ngay khi hai xâu trở nên bằng nhau, trò chơi sẽ kết thúc ngay lập tức.

Thời gian của trò chơi được định nghĩa là tổng số lượt đi mà cả hai người chơi đã thực hiện trong suốt trò chơi. Ví dụ, nếu Minh thực hiện tổng cộng $2$ lượt đi và Lan thực hiện $1$ lượt đi, thời gian của trò chơi này là $3$.

Mục tiêu của Minh là giảm thiểu thời gian của trò chơi, còn mục tiêu của Lan là tối đa hóa thời gian của trò chơi.

Hỏi thời gian của trò chơi sẽ là bao nhiêu nếu cả hai người chơi đều chơi một cách tối ưu? Có thể chứng minh rằng trò chơi sẽ kết thúc sau một số hữu hạn lượt đi.

Dữ liệu vào

Mỗi bộ test gồm nhiều bộ thử nghiệm. Dòng đầu tiên chứa số lượng bộ thử nghiệm $t$ ($1 ≤ t ≤ 10^4$). Mô tả của các bộ thử nghiệm theo sau.

Dòng đầu tiên của mỗi bộ thử nghiệm chứa một số nguyên $n$ ($1 ≤ n ≤ 10^5$), là độ dài của các xâu $A$ và $B$.

Dòng thứ hai của mỗi bộ thử nghiệm chứa một xâu $A$ độ dài $n$ gồm các ký tự latin viết thường.

Dòng thứ ba của mỗi bộ thử nghiệm chứa một xâu $B$ độ dài $n$ gồm các ký tự latin viết thường.

Tổng giá trị của $n$ trên tất cả các bộ thử nghiệm không vượt quá $10^5$ ($\sum n ≤ 10^5$).

Kết quả

Với mỗi bộ thử nghiệm, in ra một số nguyên trên một dòng riêng biệt, là thời gian của trò chơi đã mô tả nếu cả hai người chơi đều chơi tối ưu.

Chấm điểm

Subtask 1 (30 points). $n ≤ 8$; Tổng n trên tất cả các bộ thử nghiệm không vượt quá 100

Subtask 2 (70 points). $1 ≤ t ≤ 10^4$; $1 ≤ n ≤ 10^5$; Tổng n trên tất cả các bộ thử nghiệm không vượt quá 10^5

Ví dụ

Input

7
5
abcde
abxde
5
hello
olleo
2
ab
cd
7
aaaaaaa
abbbbba
1
q
q
6
yoyoyo
oyoyoy
8
abcdefgh
hguedfbh

Output

1
2
3
9
0
2
6

Ghi chú

Trong bộ thử nghiệm đầu tiên, ở lượt của mình, Minh có thể thay ký tự thứ ba của xâu $A$ thành x. Sau đó, cả hai xâu đều trở thành abxde và trò chơi kết thúc sau $1$ lượt đi. Vì mục tiêu của Minh là kết thúc trò chơi với ít lượt đi nhất có thể, lượt đi này là một trong các lượt đi đầu tiên tối ưu của cô ấy, và kết quả cuối cùng là $1$.

Trong bộ thử nghiệm thứ hai, ở lượt của mình, Minh có thể thay ký tự thứ năm của xâu $B$ thành h. Sau lượt đi này, $A =$ hello, $B =$ olleh. Sau đó Lan thực hiện lượt đi của mình. Trong lượt đi của mình, Lan phải đảo ngược một trong hai xâu. Nếu Lan chọn xâu $A$, sau lượt đi đó cả hai xâu sẽ bằng olleh, còn nếu Lan chọn xâu $B$, sau lượt đi đó cả hai xâu sẽ bằng hello. Do đó, sau lượt đi đầu tiên nêu trên của Minh, trò chơi chắc chắn kết thúc sau $2$ lượt đi. Có thể chứng minh rằng không có chiến thuật nào giúp Minh kết thúc trò chơi trong ít hơn $2$ lượt đi khi cả hai chơi tối ưu. Kết quả cuối cùng là $2$.

Trong bộ thử nghiệm thứ ba, ở lượt đầu tiên, Minh có thể thay ký tự thứ hai của xâu $A$ thành c. Sau lượt đi này, $A =$ ac, $B =$ cd. Sau đó Lan thực hiện lượt đi của mình. Nếu Lan đảo ngược xâu $A$, sau lượt đi đó $A =$ ca, $B =$ cd. Khi đó Minh chắc chắn có thể kết thúc trò chơi ở lượt thứ $3$ bằng cách thay ký tự thứ hai của xâu $B$ thành a, sau đó cả hai xâu đều trở thành ca. Nếu Lan đảo ngược xâu $B$, sau lượt đi đó $A =$ ac, $B =$ dc. Trong trường hợp này, Minh cũng chắc chắn có thể kết thúc trò chơi ở lượt thứ $3$ bằng cách thay ký tự thứ nhất của xâu $A$ thành d, sau đó cả hai xâu đều trở thành dc. Do đó, Minh chắc chắn có thể kết thúc trò chơi sau $3$ lượt đi bất kể các lượt đi của Lan. Có thể chứng minh trò chơi không thể kết thúc trong ít hơn $3$ lượt đi khi cả hai chơi tối ưu.

Trong bộ thử nghiệm thứ năm, hai xâu $A$ và $B$ đã bằng nhau nên trò chơi kết thúc ngay khi chưa bắt đầu, sau $0$ lượt đi.