Ninja is one who knows everthing but nothing. He has a string s and is very proud of it. Yash has also got a string t and wanted to show Ninja that Coders are always above him. He wanted to make string t lexicographically greater than s. He can perform the following operation :
- Swap two adjacent characters of t.
Help Yash to find the minimum number of operations required to make t lexicographically greater than s. If it is impossible print " -1 " .
Both the strings consists of lowercase english letters only.
Input :
- First line of input contains T, denoting number of Test cases.
- First line of each test case contains a string s and next line conatins the string t.
Output :
For every test case print the minimum number of operations required to make t lexicographically greater than s.
If it is not possible print "-1". ( Without Quotes )
Answer of every test case should start in a seperate line.
Constraints :
1≤T≤100
1≤|s|,|t|≤1000, |s| & |t| denotes the length of the strings
Sum of lengths of string s and t over all test cases doesn't exceed 2000 .
In the first test case : string "aadad" is already lexicographically greater than "aaccd", so we print 0.
In the second test case : we swap the the character at index 1 and 2, abcd -> abcd -> bacd, it took only 1 swap, so we print 1.
In the third test case we do the following swaps:
aacbz -> aacbz -> aaczb
aaczb -> aaczb -> aazcb
aazcb -> aazcb -> azacb
azacb -> azacb -> zaacb
zaacb -> zaacb -> zacab
zacab -> zacab -> zcaab
"zcaab" is now lexicographically greater than "zbaa", it took 6 swaps, so we print 6.
In the last test case, we can't change make the string "aaa" lexicographically greater than "zzzzz", no matter how many swaps we do, so we print -1.
