#include <bits/stdc++.h>
#define INF -10000000
#define FACTOR 10
using namespace std;
double memo[100][100][100];
double Levenshtein(string inputWord, string checkWord, int i, int j, int count){
if(i == inputWord.length() && j == checkWord.length()) return 0;
if(i == inputWord.length()) return checkWord.length() - j;
if(j == checkWord.length()) return inputWord.length() - i;
if(memo[i][j][count] != INF) return memo[i][j][count];
double ans1 = 0, ans2 = 0, ans3 = 0, ans = 0;
if(inputWord[i] == checkWord[j]){
ans1 = Levenshtein(inputWord, checkWord, i+1, j+1, count+1) - (FACTOR*(count+1));
ans2 = Levenshtein(inputWord, checkWord, i+1, j, 0) + 1;
ans3 = Levenshtein(inputWord, checkWord, i, j+1, 0) + 1;
ans = min(ans1, min(ans2, ans3));
}else{
ans1 = Levenshtein(inputWord, checkWord, i+1, j, 0) + 1;
ans2 = Levenshtein(inputWord, checkWord, i, j+1, 0) + 1;
ans = min(ans1, ans2);
}
return memo[i][j][count] = ans;
}
int main(void) {
// your code goes here
string word = "job";
string wordList[40];
vector< pair <double, string> > ans;
for(int i = 0;i < 40;i++){
cin >> wordList[i];
for(int j = 0;j < 100;j++) for(int k = 0;k < 100;k++){
for(int m = 0;m < 100;m++) memo[j][k][m] = INF;
}
ans.push_back( make_pair(Levenshtein(word, wordList[i],
0, 0, 0), wordList[i]) );
}
sort(ans.begin(), ans.end());
for(int i = 0;i < ans.size();i++){
cout << ans[i].second << " " << ans[i].first << endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgojZGVmaW5lIElORiAtMTAwMDAwMDAKI2RlZmluZSBGQUNUT1IgMTAKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpkb3VibGUgbWVtb1sxMDBdWzEwMF1bMTAwXTsKCmRvdWJsZSBMZXZlbnNodGVpbihzdHJpbmcgaW5wdXRXb3JkLCBzdHJpbmcgY2hlY2tXb3JkLCBpbnQgaSwgaW50IGosIGludCBjb3VudCl7CglpZihpID09IGlucHV0V29yZC5sZW5ndGgoKSAmJiBqID09IGNoZWNrV29yZC5sZW5ndGgoKSkgcmV0dXJuIDA7CQoJaWYoaSA9PSBpbnB1dFdvcmQubGVuZ3RoKCkpIHJldHVybiBjaGVja1dvcmQubGVuZ3RoKCkgLSBqOwoJaWYoaiA9PSBjaGVja1dvcmQubGVuZ3RoKCkpIHJldHVybiBpbnB1dFdvcmQubGVuZ3RoKCkgLSBpOwoJaWYobWVtb1tpXVtqXVtjb3VudF0gIT0gSU5GKSByZXR1cm4gbWVtb1tpXVtqXVtjb3VudF07CgkKCWRvdWJsZSBhbnMxID0gMCwgYW5zMiA9IDAsIGFuczMgPSAwLCBhbnMgPSAwOwoJaWYoaW5wdXRXb3JkW2ldID09IGNoZWNrV29yZFtqXSl7CgkJYW5zMSA9IExldmVuc2h0ZWluKGlucHV0V29yZCwgY2hlY2tXb3JkLCBpKzEsIGorMSwgY291bnQrMSkgLSAoRkFDVE9SKihjb3VudCsxKSk7CgkJYW5zMiA9IExldmVuc2h0ZWluKGlucHV0V29yZCwgY2hlY2tXb3JkLCBpKzEsIGosIDApICsgMTsKCQlhbnMzID0gTGV2ZW5zaHRlaW4oaW5wdXRXb3JkLCBjaGVja1dvcmQsIGksIGorMSwgMCkgKyAxOwoJCWFucyA9IG1pbihhbnMxLCBtaW4oYW5zMiwgYW5zMykpOwoJfWVsc2V7CgkJYW5zMSA9IExldmVuc2h0ZWluKGlucHV0V29yZCwgY2hlY2tXb3JkLCBpKzEsIGosIDApICsgMTsKCQlhbnMyID0gTGV2ZW5zaHRlaW4oaW5wdXRXb3JkLCBjaGVja1dvcmQsIGksIGorMSwgMCkgKyAxOwoJCWFucyA9IG1pbihhbnMxLCBhbnMyKTsKCX0KCXJldHVybiBtZW1vW2ldW2pdW2NvdW50XSA9IGFuczsKfQoKaW50IG1haW4odm9pZCkgewoJLy8geW91ciBjb2RlIGdvZXMgaGVyZQoJc3RyaW5nIHdvcmQgPSAiam9iIjsKCXN0cmluZyB3b3JkTGlzdFs0MF07Cgl2ZWN0b3I8IHBhaXIgPGRvdWJsZSwgc3RyaW5nPiA+IGFuczsKCWZvcihpbnQgaSA9IDA7aSA8IDQwO2krKyl7CgkJY2luID4+IHdvcmRMaXN0W2ldOwoJCWZvcihpbnQgaiA9IDA7aiA8IDEwMDtqKyspIGZvcihpbnQgayA9IDA7ayA8IDEwMDtrKyspewoJCQlmb3IoaW50IG0gPSAwO20gPCAxMDA7bSsrKSBtZW1vW2pdW2tdW21dID0gSU5GOwoJCX0KCQlhbnMucHVzaF9iYWNrKCBtYWtlX3BhaXIoTGV2ZW5zaHRlaW4od29yZCwgd29yZExpc3RbaV0sIAoJCQkwLCAwLCAwKSwgd29yZExpc3RbaV0pICk7Cgl9Cglzb3J0KGFucy5iZWdpbigpLCBhbnMuZW5kKCkpOwoJZm9yKGludCBpID0gMDtpIDwgYW5zLnNpemUoKTtpKyspewoJCWNvdXQgPDwgYW5zW2ldLnNlY29uZCA8PCAiICIgPDwgYW5zW2ldLmZpcnN0IDw8IGVuZGw7Cgl9CglyZXR1cm4gMDsKfQo=