I. Playing with strings
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

Taboush is a 10 year-old school boy. On his birthday, his parents got him a new Alphabet blocks game.

Alphabet blocks game consists of cubes. Each cube has a letter written on it, and each letter is written on an infinite number of cubes.

Taboush wasted no time and he immediately started forming his magical string S1. He spent all day forming the string. At the end, he was so tired, so he felt asleep.

While he was asleep, his naughty cat Basbouse - as he called her - found the magical string. She started to add, delete and shuffle letters in S1, and she ended up forming a new string S2.

When Taboush finally woke up, he was upset that Basbouse had ruined his magical string. Now, he wants to form his magical string all over again.

In one move, Taboush can add a letter to S2 or delete a letter from S2. At the end, Taboush can shuffle the letters to any order he wants.

Can you help Taboush by telling him what is the minimum number of moves he needs to do, in order to convert S2 into S1?

Please note that shuffling the letters is not counted as a move.

Input

The first line of the input consists of a single integer t denoting the number of test cases.

Each test case consists of 2 lines. The first line contains S1, and the second line contains S2 (1 ≤ |S1|, |S2| ≤ 105) consisting of lower case English letters only.

Output

For each test case print a single line containing the minimum number of moves Taboush needs in order to convert S2 into S1.

Example
Input
3
abc
abd
abcde
bdcea
taboush
basbouse
Output
2
0
5
Note

|S| means the length of the string S.

In the first test case, Taboush has to delete the letter d, then add the letter c. Thus, he needs 2 moves.

In the second test case, Taboush has to shuffle the letters only. Thus, he doesn't need any number of moves.