Jak co roku zbliża się wielkie święto szydełkowania organizowane przez pana Józefa. Pan Wincenty (biegły w sztuce szydełkowania) postanowił w ramach sąsiedzkiej pomocy przygotować baner reklamujący to wydarzenie. Niestety, pan Wincenty pomylił się znacznie w treści wyszydełkowanego tekstu.</p>

Witek postanowił pomóc tacie i naprawić baner. W celu naprawienia banera może wykonywać dwa rodzaje opracji.

• Usunięcie, polegające na usunięciu z banera ciągu kolejnych liter
• Dodanie, polegające na wstawieniu na początku, na końcu, lub pomiędzy dwie litery banera ciągu liter

Każda z operacji trwa X + SY minut, gdzie S oznacza długość ciągu liter wstawianego lub usuwanego z banera. Oblicz najkrótszy możliwy czas naprawy banera.

입력 형식

Pierwsza linia zawiera liczbę naturalną L - liczbę zestawów testowych. Następnie podawany jest opis kolejnych zestawów.</p>

Opis każdego zestawu składa się z trzech linii. W pierwszej znajduje się liczba naturalna D1 i słowo S1. S1 to początkowa treść baneru, a D1 - długość słowa S1 (1<=D1 <=1000). W drugiej linii następuje analogiczny opis docelowej treści baneru. W trzeciej linii znajdują się dwie, podane z dokładnością do 6 cyfr po przecinku liczby rzeczywiste X i Y (0<=X,Y<=100).  Zarówno S1 jak i S2 składają się wyłącznie z dużych liter alfabetu angielskiego.

출력 형식

Dla każdego zestawu należy wypisać w osobnej linii opisany w treści minimalny czas naprawy z dokładnością do 6 cyfr po przecinku.

예제 입력

2
4 AAAA
6 ABBAAA
5.000000 4.000000
3 BAC
3 DAF
1.000000 0.500000

예제 출력

13.000000
5.000000