Little Cyan Fish-тің қолында $n$ жол мен $m$ бағаннан тұратын $A$ матрицасы бар. Матрицаның әрбір элементі көгілдір (Cyan) немесе ақ (White) болуы мүмкін. Көгілдір түсті белгілеу үшін C таңбасын, ал ақ түсті белгілеу үшін W таңбасын қолданамыз. Ыңғайлы болу үшін Little Cyan Fish матрицаның $i$-ші жолы мен $j$-ші бағанындағы ($1 \le i \le n, 1 \le j \le m$) элементті $A_{i,j}$ деп белгілейді.

Little Cyan Fish келесі операцияны кез келген рет орындай алады:

• Тігінен көршілес немесе көлденеңінен көршілес $A_{i,j}$ және $A_{k,l}$ ұяшықтар жұбын таңдау. Яғни, $|i - k| + |j - l| = 1$.
• $A_{i,j}$ мен $A_{k,l}$ орындарын ауыстыру.

Little Cyan Fish $A$ матрицасын берілген басқа $B$ матрицасына айналдырғысы келеді. Әрине, Little Cyan Fish $A$ матрицасындағы көгілдір элементтердің саны соңғы талап етілетін $B$ матрицасындағы көгілдір элементтердің санына тең екеніне кепілдік береді, сондықтан Little Cyan Fish-тің талабын қанағаттандыратын операциялар тізбегі міндетті түрде бар болады.

Сізге Little Cyan Fish-ке оның талабын орындау үшін қажетті ең аз операциялар санын есептеуге көмектесу керек.

Кіріс деректер

Бірнеше тест жағдайлары бар. Кіріс деректердің бірінші қатарында тест жағдайларының санын білдіретін бір бүтін сан $T$ ($1 \le T$) берілген.

Әрбір тест жағдайы үшін бірінші қатарда матрицаның жолдары мен бағандарының санын білдіретін екі бүтін сан $n$ және $m$ ($1 \le n \le 10^5, 1 \le m \le 6$) берілген.

Келесі $n$ қатардың әрқайсысында $A$ матрицасының әр жолын сипаттайтын ұзындығы $m$ болатын жол (тек C немесе W таңбаларынан тұратын) берілген.

Келесі $n$ қатардың әрқайсысында $B$ матрицасының әр жолын сипаттайтын ұзындығы $m$ болатын жол (тек C немесе W таңбаларынан тұратын) берілген. $A$ матрицасы мен $B$ матрицасындағы C таңбаларының саны бірдей екеніне кепілдік беріледі (әрине, W таңбаларының саны да бірдей болады).

Барлық тест жағдайлары бойынша $n$ қосындысы $10^5$-нен аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест жағдайы үшін Little Cyan Fish-ке $A$ матрицасын $B$ матрицасына айналдыру үшін қажетті ең аз операциялар санын білдіретін бір бүтін саннан тұратын бір қатар шығарыңыз.

Мысал

Кіріс деректер 1

2
2 2
CW
WC
WC
CW
5 3
WWC
WCW
CWC
CCC
CCC
CCC
CCC
CCC
CWW
WWW

Шығыс деректер 1

2
16