배너 수리

해마다 열리는 큰 뜨개질 축제가 다가옵니다. 뜨개질에 능한 빈센트 씨는 이웃을 돕는 마음으로 축제를 알리는 배너를 떠서 만들기로 했습니다. 그런데 배너에 새긴 글자를 크게 잘못 떠 버렸습니다.

아들 비텍이 아버지를 도와 배너를 고치려 합니다. 배너를 고칠 때는 다음 두 가지 연산만 사용할 수 있습니다.

• 삭제: 배너에서 연속한 글자들로 이루어진 한 구간을 통째로 지웁니다.
• 삽입: 배너의 맨 앞, 맨 뒤, 또는 두 글자 사이에 글자들로 이루어진 한 구간을 끼워 넣습니다.

각 연산에는 $X + S \cdot Y$ 분이 걸립니다. 여기서 $S$ 는 이번 연산에서 삽입하거나 삭제한 글자 구간의 길이입니다. 처음 배너 내용을 목표 배너 내용으로 바꾸는 데 필요한 최소 시간을 구하세요.

첫 줄에 테스트 케이스의 개수 $L$ 이 주어집니다. 이어서 각 테스트 케이스의 정보가 주어집니다.

각 테스트 케이스는 세 줄로 이루어집니다.

• 첫째 줄: 정수 $D_1$ 과 문자열 $S_1$. $S_1$ 은 처음 배너 내용이고 $D_1$ 은 $S_1$ 의 길이입니다 ($1 \le D_1 \le 1000$).
• 둘째 줄: 정수 $D_2$ 와 문자열 $S_2$. $S_2$ 는 목표 배너 내용이고 $D_2$ 는 $S_2$ 의 길이이며, 형식은 첫째 줄과 같습니다.
• 셋째 줄: 소수점 아래 최대 6자리까지 주어지는 두 실수 $X$ 와 $Y$ ($0 \le X, Y \le 100$).

$S_1$ 과 $S_2$ 는 모두 영어 대문자로만 이루어져 있습니다.

각 테스트 케이스마다 한 줄에 최소 수리 시간을 소수점 아래 6자리까지 출력하세요.