对于长度相同的两个数字串a和b，其距离定义为相应位置数字距离之和。两个非空数字距离是他们之差的绝对值。空格和空格的距离为0，空格与其他数字的距离为一定值k。在一般情况下，数字串a和b的长度不一定相同。数字串a的扩展是在a中插入若干个空格所产生的字符串。在数字串a和b的所有长度相同的扩展中，有一对距离最小的扩展，称为a和b的扩展距离。给你两个数字串a和b，你能算出它们的扩展距离吗？

第一行输入一个整数t，表示有t组例子；
每组例子包括两个部分;
第一部分占一行，分别三个整数n，m，k。其中n为第一个数字串的长度，m为第二个数字串的长度，k如上所述。（0<=m,n,k<=1000）;
第二部分占两行，分别为两个数字串。

输出包括t行，每行输出每组例子对应的结果。