#include <bits/stdc++.h>
#include <cassert>
#include <climits>
#include <cfloat>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
/*
srand((unsigned)time(NULL));
inline unsigned int rand16(){return ((rand()) << 15) ^ rand();}
inline unsigned int rand32(){return (rand16() << 16) | rand16();}
inline ULL rand64(){return ((LL)rand32() << 32) | rand32();}
inline ULL random(LL l, LL r){return l == r ? l : rand64() % (r - l) + l;}
*/
const int INF = 0x3f3f3f3f;
const LL INFF = 1LL << 60;
const double EPS = 1e-9;
const double PI = acos(-1.0); //2*acos(0.0); //M_PI;
//4 dirs: int dx[]={1,0,-1,0}, dy[]={0,1,0,-1};
//8 dirs: int dx[]={1,1,0,-1,-1,-1,0,1}, dy[]={0,1,1,1,0,-1,-1,-1};
//hex: int dx[6]={2,1,-1,-2,-1,1}, dy[6]={0,1,1,0,-1,-1};
//knight: int dx[]={2,1,-1,-2,-2,-1,1,2}, dy[]={1,2,2,1,-1,-2,-2,-1};
#define FOR(i,a,b) for(int(i)=int(a);(i)<int(b);(i)++)
#define FOREQ(i,a,b) for(int(i)=int(a);(i)<=int(b);(i)++)
#define RFOR(i,a,b) for(int(i)=(a),_b(b);(i)>=_b;--(i))
#define FOREACH(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define FILL(arr,val) memset((arr),(val),sizeof(arr))
#define CLR(a) memset((a),0,sizeof(a))
#define CPY(dest,src) memcpy((dest),(src),sizeof(dest))
#define ALL(a) (a).begin(),(a).end()
#define SZ(a) ((int)(a).size())
#define UNIQ(a) sort(ALL(a)); (a).erase(unique(ALL(a)),(a).end())
#define IDX(arr,ind) (lower_bound(ALL(arr),ind)-arr.begin())
#define fst first
#define snd second
#define pb push_back
#define mp make_pair
template< typename T, size_t N >
inline void print_ary(T(&ary)[N], int er)
{
for(int r = 0; r < er; r++)
{
cout << ary[r] << " ";
}
cout<<endl;
}
template< typename T, size_t N >
inline void print_ary_eq(T(&ary)[N], int er)
{
for(int r = 1; r <= er; r++)
{
cout << ary[r] << " ";
}
cout<<endl;
}
template< typename T, size_t N, size_t M >
inline void print_ary_2d(T(&ary)[N][M], int er, int ec)
{
for(int r = 0; r < er; r++)
{
for(int c = 0; c < ec; c++)
{
cout << ary[r][c] << " ";
}
cout<<endl;
}
}
template< typename T, size_t N, size_t M >
inline void print_ary_2d_eq(T(&ary)[N][M], int er, int ec)
{
for(int r = 1; r <= er; r++)
{
for(int c = 1; c <= ec; c++)
{
cout << ary[r][c] << " ";
}
cout<<endl;
}
}
inline LL lcm(LL a, LL b)
{
return a*b/__gcd(a,b);
}
inline double dist(double x1, double y1, double x2, double y2)
{
return hypot(x1-x2,y1-y2);
}
//scanf("%[^\n]", &s);
#define MIN3(a, b, c) ((a) < (b) ? ((a) < (c) ? (a) : (c)) : ((b) < (c) ? (b) : (c)))
static char s[100005], t[100005];
static int a,b,k, v0[100005], v1[100005];
inline int levenshtein()
{
// if (a == 0 && b == 0) return 0;
// if (a > 0 && b > 0 && k == 0) return -1;
if (strcmp(s,t) == 0) return 0;
int slen = strlen(s), tlen = strlen(t);
// printf("read: s(s2-row)=%s; t(s1-col)=%s; a=%d; b=%d; k=%d\n", s,t,a,b,k);
FOR(i,0,tlen)
{
v0[i] = i;
}
// printf("v0: %02d %02d ", v0[0],v0[1]);
// FOR(i,2,tlen)
// {
// printf("%02d ", v0[i]);
// }
// printf("\n");
FOR(i,0,slen)
{
if (i<=k)
{
v1[0] = i+1;
FOR(j,0,min(i+k+1,tlen))
{
if (j == min(i+k,tlen-1))
{
v1[j+1] = min(
v1[j] + a,
v0[j] + (s[i]==t[j]?0: min(2*a,b) )
);
}
else
{
v1[j+1] = min(min(
v1[j] + a,
v0[j+1] + a
),
v0[j] + (s[i]==t[j]?0: min(2*a,b) )
);
}
}
}
else //i > k
{
v1[i-k] = k;
FOR(j,i-k,min(i+k+1,tlen))
{
if (j == i-k)
{
v1[j+1] = min(
v0[j+1] + a,
v0[j] + (s[i]==t[j]?0: min(2*a,b) )
);
}
else if (j == min(i+k,tlen-1))
{
v1[j+1] = min(
v1[j] + a,
v0[j] + (s[i]==t[j]?0: min(2*a,b) )
);
}
else
{
v1[j+1] = min(min(
v1[j] + a,
v0[j+1] + a
),
v0[j] + (s[i]==t[j]?0: min(2*a,b) )
);
}
}
}
// printf("i=%02d: [%02d] ", i,v1[0]);
// FOR(j,1,tlen+1)
// {
// printf("%02d ", v1[j]);
// }
// printf("\n");
if (i<=k)
{
FOR(j,0,min(i+k,tlen)+1)
{
v0[j] = v1[j];
}
}
else //i > k
{
FOR(j,i-k-1,min(i+k+1,tlen)+1)
{
v0[j] = v1[j];
}
}
}
return v1[tlen];
}
inline void read(int &x)
{
register int c = getchar_unlocked();
x = 0;
for(; (c<48 || c>57); c = getchar_unlocked())
;
for(; c>47 && c<58; c = getchar_unlocked())
{
x = (x<<1) + (x<<3) + c - 48;
}
}
int main()
{
int T;
scanf("%d", &T);
FOR(i,0,T)
{
scanf("%s", s);
scanf("%s", t);
// read(a); read(b); read(k);
scanf("%d%d%d", &a,&b,&k);
int k_orig = k;
k++;
int ans = levenshtein();
if (ans > k_orig) ans = -1;
printf("%d\n", ans);
}
return 0;
}