You are given two Strings A and B that have the same length and contain only lowercase letters ('a'-'z').
The distance between two letters is defined as the absolute value of their difference. The distance between A and B is defined as the sum of the differences between each letter in A and the letter in B at the same position.
For example, the distance between "abcd" and "bcda" is 6 (1 + 1 + 1 + 3).
You must change exactly K characters in A into other lowercase letters. print the minimum possible distance between A and B after you perform that change.

输入格式

There will be multiple test cases. The first line of input contains a positive integer T, indicating the number of cases. In the following T lines, there are two strings A and B, and an integer K seprated by one space in a single line. you can assume A and B have the same length(0<length<=10000), and 1<= K <=A or B's length.

输出格式

For each test case, output an integer indicating the minimum possible distance between A and B after you perform that change.

样例输入

5
ab ba 2
aa aa 2
aaa baz 1
fdfdfdfdfdsfabasd jhlakfjdklsakdjfk 8
aa bb 2

样例输出

0
2
1
24
0

提示

in case 1, you change ab to ba, and then the minimum distance is 0;
in case 2, you change aa to bb, and then the minimum distance is 2;
in case 3, you change aaa to aaz, and then the minimum distance is 1;
...

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int main() {
	int t;
	scanf("%d",&t);
	while(t--) {
		string a,b;
		int k,i;
		cin >> a >> b >> k;
		int len = a.length();
		int ss[len];
		long int res = 0;
		for (i=0; i<len; i++) {
			ss[i] = ((b[i]>a[i]) ? (b[i]-a[i]) : (a[i]-b[i]));
			res += ss[i];
		}
		sort(ss,ss+len);
		for(i=len-1; i>(len-1-k); --i) {
			res -= (ss[i]==0) ? -1 : ss[i];
		}
		cout << res <<endl;
	}
	return 0;
}