對于兩個(gè)不同的字符串，我們有一套操作方法來把他們變得相同，具體方法為：    
修改一個(gè)字符（如把“a”替換為“b”）;
刪除一個(gè)字符（如把“traveling”變?yōu)椤皌ravelng”）。
比如對于“abcdefg”和“abcdef”兩個(gè)字符串來說，我們認(rèn)為可以通過增加/減少一個(gè)“g”的方式來達(dá)到目的。無論增加還是減少“g”，我們都僅僅需要一次操作。我們把這個(gè)操作所需要的次數(shù)定義為兩個(gè)字符串的距離。
給定任意兩個(gè)字符串，寫出一個(gè)算法來計(jì)算出他們的距離。

第一行有一個(gè)整數(shù)n。表示測試數(shù)據(jù)的組數(shù)。
接下來共n行，每行兩個(gè)字符串，用空格隔開，表示要計(jì)算距離的兩個(gè)字符串。
字符串長度不超過1000。

針對每一組測試數(shù)據(jù)輸出一個(gè)整數(shù)，值為兩個(gè)字符串的距離。

零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情

編程練習(xí) 動態(tài)規(guī)劃 基礎(chǔ)