Alice and Bob are playing a game: Alice selects a text t and a word w, and then Bob has to say how many times w occurs in t. However, after a while, Alice realizes that this version of the game is too boring for Bob and decides to make a modification: in her new version of the game, the wildcard symbol ‘?’ can occur in w any number of times. Each occurrence of ‘?’ in w can be matched with any character in t. In the new version of the game, for instance, if the text is t = banana and the word is w = ?a?, then w occurs twice in t: at position 0 matching “ban” and at position 2 matching “nan”. Notice that matches can overlap. Can you write a program to help Bob solve this new game? Input The input consists of several test cases, each one defined by two lines. The first line contains the text t and the second line contains the word w. The text t consists of lowercase letters from the English alphabet (1 ≤ |t| ≤ 105), and the word w consists of lowercase letters from the English alphabet and the wildcard character ‘?’ (1 ≤ |w| ≤ 105). It is guaranteed that there will be at most k wildcard () characters in w, where 0 ≤ k ≤ min |w|, 106/|t| . Output For each test case, print a line with one integer denoting the number of times w appears in t if each wildcard character matches any character in t. Sample Input banana ?a? bananas ?a? abide a??d abide a?d abracadabra a?a acisredis ?b acisredis ?? icpc world?finals Sample Output 2 3 1
2/2 0 2 0 8 0