Migrated from Lutece 98 Escape From the Chamber

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

An adventurer is trapped in a chamber, and the only way he can escape is a door with a special lock. The lock is a seiries of combined rotatable disks with some characters on them. The picture below is an example of a lock with $4$ disks. The door will open if the character sequence on the lock forms the correct password. Fortunately, the adventurer finds the password, but he is not always so lucky. The chamber seems to collapse in a while, so he must get out as quick as possible. Every second he can rotate one disk and swap the two characters on it. The adventurer wants to know what's the minimum time before he leaves this place.

Input

One integer $T$ on the first line indicates the number of cases. Then followed by $T$ cases. Every case contains two strings of lowercase characters with the same $length$($length\leq 10000$).The first string

is the initial character sequence on the lock,and the second string is the password.

It's guaranteed that there is always a solution to form the password.

Output

For each case, print an integer on a line indicating the minimum time to escape from the chamber.

Samples

2
abcde
acbde
aaaaaab
baaaaaa

1
6

Resources

The 8th UESTC Programming Contest Preliminary