Доктор Мориарти Шерлок Холмс руу зурвас илгээх гэж байна. Түүнд $s$ гэх тэмдэгт мөр байгаа.

$s$ тэмдэгт мөрийн ямар нэг байрлалаас эхлэн хэдэн үсэг дарааллан уншсан $p$ тэмдэгт мөрийг $s$ тэмдэгт мөрийн дэд тэмдэгт мөр гэнэ. Жишээлбэл, "$aba$" тэмдэгт мөр нь "$a$", "$b$", "$a$", "$ab$", "$ba$", "$aba$" гэсэн 6 дэд тэмдэгт мөртэй.

Доктор Мориарти $s$ тэмдэгт мөрөөс зарим дэд тэмдэгт мөрүүдийг таслан авахаар төлөвлөж байгаа ба бүгдээрээ энэхүү дэд тэмдэгт мөрийг $t$ гэж нэрлэе. Дараагаар нь $t$ дэд тэмдэгт мөрөө тэг буюу түүнээс олон удаа өөрчлөх хэрэгтэй. Үр дүнд нь тэрээр үндсэн тэмдэгт мөр $u$-г (Шерлок Холмс руу илгээгдэх ёстой тэмдэгт мөр) гаргаж авна. Өөрчлөлт нь дараах үйлдлүүдийн аль нэгийг хийнэ. Үүнд:

• Тэмдэгт мөрийн аль нэг төгсгөлд нэг үсэг нэмэх.
• Тэмдэгт мөрийн аль нэг төгсгөлөөс нэг үсэг устгах.
• Ямар нэг үсгийг өөр нэг үсгээр солих.

Мориарти маш ухаалаг хүн. Тэрээр ямар нэг $t$ дэд тэмдэгт мөрийг сонгож, хамгийн цөөн тооны өөрчлөлт хийн $u$-г гаргаж авдаг.

$s$ тэмдэгт мөрийн бүх дэд тэмдэгт мөрүүдээс хамгийн тохиромжтой $t$ дэд тэмдэгт мөрийг сонгоход нь Мориартид туслаарай. $t$ дэд тэмдэгт мөрийг Мориарти үүнээс $u$ тэмдэгт мөрийг гаргаж авах өөрчлөлтийн тоог хамгийн бага байлгахаар сонгох хэрэгтэй.

Оролт

Эхний мөр нь Латин жижиг үсгүүдээс бүрдсэн, хоосон биш $s$ тэмдэгт мөрийг агуулна. $2$ дахь мөр нь Латин жижиг үсгүүдээс бүрдсэн, хоосон биш $u$ тэмдэгт мөрийг агуулна. $2$ тэмдэгт мөрийн урт нь $1$-ээс $2000$ хүртэл байна.

Гаралт

Таны сонгосон тэмдэгт мөрөөс Доктор Мориарти хийх шаардлагатай өөрчлөлтийн хамгийн бага тоог хэвлэ.

Эхний жишээнд, Мориарти $3$ урттай ямар ч дэд тэмдэгт мөрийг авч болох ба энэ нь бидний хүсч буй зурвас $u$-тай тэнцүү байна. Тиймээс Мориартид ямар нэг өөрчлөлт хийх хэрэг байхгүй.

2 дахь жишээнд, та $2-4$ дэх тэмдэгтүүд болох ("$bca$")-аас бүрдсэн дэд тэмдэгт мөрийг эсвэл $5-6$ дахь тэмдэгтүүд болох ("$bc$")-ээс бүрдсэн дэд тэмдэгт мөрийг сонгох хэрэгтэй. Тэгвэл танд сүүлийн тэмдэгтийг өөрчлөх эсвэл нэмэх гэсэн нэг л өөрчлөлт хийх хэрэгтэй болно.

3 дахь жишээнд, эхний $s$ тэмдэгт мөр нь зурвасын аль нэг тэмдэгтүүдээс агуулаагүй тул та ямар ч тэмдэгт мөрийг сонгосон хамгийн багадаа $7$ өөрчлөлтийг хийж бидний хүсч буй зурвас үүснэ.