Given a string s of size n, we define the i-th rotation of s (for 0 ≤ i < n) as
s_{i} s_{i+1} … s_{n−1} s_{0} … s_{i−2} s_{i−1} . |
Given two strings s and t, compute how many i-th rotations of s are equal to t.
For instance, for s = “abbabb” and t = “babbab” the answer is 2, corresponding to i = 2 and i = 5.
Input
Input consists of several cases, each one with two strings s and t with only lowercase letters. Assume 1 ≤ | s | = | t | ≤ 10^{5}. Every letter appears the same number of times in s and in t.
Output
For every case, print the number of i-th rotations of s that are equal to t.
Input
abbabb babbab abc acb abba bbaa zzzzz zzzzz
Output
2 0 1 5