文理学院程序设计在线练习


字母移动游戏

Time Limit: 2 Second(s)    Memory Limit: 32 MB

Total Submission(s): 24   Accepted Submission(s): 10
Problem Description

这里有一个简单又有趣的字母移动游戏。游戏的开始有两个只包含小写英文字母的字符串S和T。S和T包含相同的字母,但是顺序可能不同。换句话说,T能通过移动S中的字母得到。对于每一步,你能将S中的任意字母移动到最前或者最后。最少需要多少步才能将S变成T?

Input

第一行包含一个整数t(1<=t<=100)表示有t个例子。
对于每个例子,包含两个字符串S和T,它们包含相同的字母,长度不超过1000。

Output

对于每个例子,输出将S变成T的最少步数。

Sample Input
1
iononmrogdg goodmorning
Sample Output
8
Hint

(0) 从iononmrogdg开始
(1) 移动最后的g到最前:giononmrogd
(2) 移动m到最后:giononrogdm
(3) 移动第一个o到最后:ginonrogdmo
(4) 移动r到最后:ginonogdmor
(5) 移动第一个n到最后:gionogdmorn
(6) 移动I到最后:gonogdmorni
(7) 移动第一个n到最后:googdmornin
(8) 移动第二个g到最后:goodmorning

Source

2019元培院赛