In [41]:

    

def find_min_edit(wordA, wordB):
    lengthA = len(wordA)
    lengthB = len(wordB)
    
    matAB = [[0 for x in range(lengthA + 1)] for y in range(lengthB + 1)]
    
    for i in range(lengthA + 1):
        matAB[0][i] = i
    
    for i in range(lengthB + 1):
        matAB[i][0] = i
    
    for i in range(1, lengthB + 1):
        for j in range (1, lengthA + 1):
            if wordA[j-1] == wordB[i-1]:
                matAB[i][j] = matAB[i-1][j-1]
            else:
                matAB[i][j] = min(matAB[i][j-1], matAB[i-1][j-1], matAB[i-1][j]) + 1
                
    print matAB[lengthB][lengthA]


    

In [42]:

    

no_test_cases = int(raw_input())

for i in range(no_test_cases):
    wordA = str(raw_input())
    wordB = str(raw_input())
    
    find_min_edit(wordA, wordB)


    

    




1
A
A
0

In [ ]:

    




    

In [ ]: