题目描述

扑克玩家在牌桌上的一个常见消遣是洗筹码堆。洗筹码的操作开始时有两个扑克筹码堆$S1$和$S2$，每个堆包含$C$个筹码。每个堆可能包含多种不同颜色的筹码。

实际的洗牌操作是通过将$S1$和$S2$的筹码交错排列来完成的，如下所示（以$C = 5$为例）：
洗牌后得到的单个堆$S12$包含$2 \times C$个筹码。$S12$的最底部筹码是$S2$的最底部筹码，其上是$S1$的最底部筹码。接着是$S2$的倒数第二个筹码，然后是$S1$的倒数第二个筹码，依此类推，直到$S1$的顶部筹码被放在$S12$的顶部。

洗牌操作完成后，$S12$会被分成两个新的堆：将$S12$最底部的$C$个筹码作为新的$S1$，顶部的$C$个筹码作为新的$S2$。然后可以重复洗牌操作以生成新的$S12$。

本题要求你编写一个程序，判断是否可以通过多次洗牌操作得到特定的目标堆$S12$。

输入格式

第一行输入一个整数$N$（$1 \leq N \leq 1000$），表示数据集的数量。每个数据集包含四行输入：第一行是一个整数$C$（$1 \leq C \leq 100$），表示初始堆$S1$和$S2$中的筹码数量。第二行给出堆$S1$中$C$个筹码的颜色，从最底部的筹码开始。第三行给出堆$S2$中$C$个筹码的颜色，从最底部的筹码开始。第四行包含$2 \times C$个大写字母（$A$到$H$），表示经过零次或多次洗牌后希望得到的目标堆$S12$的颜色序列，最底部的筹码颜色最先给出。

输出格式

对于每个数据集，输出一行，包含数据集编号（从$1$到$N$）、一个空格和一个整数，表示得到目标堆所需的最小洗牌次数。如果无法通过洗牌得到目标堆，则输出$-1$。

样例输入

2  
4  
AHAH  
HAHA  
HHAAAAHH  
3  
CDE  
CDE  
EEDDCC  

样例输出

1 2  
2 -1  

题目来源

2006年大纽约地区程序设计竞赛