Time Limit:1000ms Memory Limit:65536KB

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<=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.

Sample Input

2
abcde
acbde
aaaaaab
baaaaaa

Sample Output

1
6

Hint


Author

Source

The 8th UESTC Programming Contest Preliminary