During an ACM training team gathering, Shenchuan and ybs performed a song in KTV. However, when Shenchuan started singing after ybs, the singing score dropped from 90 to 60! ybs was very dissatisfied with this and requested help from 37Lament.
The original of the song are represented by a string T, Shenchuan's singing is represented by a string S.37Lament wants to change the string S at such way, that it can be found in T as a substring. All the changes should be the following: 37Lament chooses one position in the string S and replaces the symbol in this position with the question mark "?". 37Lament is sure that the question mark in comparison can play the role of an arbitrary symbol. For example, if he gets string S="ab?b" as a result, it will appear in T="aabrbb" as a substring
Guaranteed that the length of the string S doesn't exceed the length of the string T. Help the hacker to replace in S as few symbols as possible so that the result of the replacements can be found in T as a substring. The symbol "?" should be considered equal to any other symbol.