编辑距离问题，也称为Levenshtein距离，是指将一个字符串转换为另一个字符串所需的最少操作次数。允许的操作包括插入一个字符、删除一个字符或替换一个字符。
编辑距离问题，也称为Levenshtein距离，是指将一个字符串转换为另一个字符串所需的最少操作次数。允许的操作包括插入一个字符、删除一个字符或替换一个字符。
第一行输入正整数n，表示有n个测试样例, n < 200。接着，输入n个测试样例。每个测试样例在同一行输入，包含两个字符串，两个字符串之间用空格隔开，每个字符串长度均小于100.
输出k个整数，表示k个样例中，每个将字符串1转换为字符串2所需的最少操作次数。每个整数占一行。
输入
2 abc bdc algorithm algorit
输出
2 2