Transmission Passphrase Repeat Depth

A signals-intelligence analyst has intercepted a long transmission string and suspects it hides a coded passphrase, repeated back-to-back some number of times as camouflage. For a positive integer k, the k-fold echo of the passphrase is the passphrase concatenated with itself k times, with no characters in between (for example, the 3-fold echo of "ab" is "ababab"). The analyst wants to know the greatest k for which the k-fold echo occurs somewhere inside the transmission as one unbroken block. If not even a single copy of the passphrase (k = 1) appears anywhere in the transmission, the answer is 0.

Input format

The first line contains the transmission string. The second line contains the passphrase string. Both strings consist only of lowercase English letters and contain no spaces.

Output format

Print a single integer: the largest k such that the passphrase repeated k times back-to-back appears as a contiguous block inside the transmission, or 0 if no such k >= 1 exists.

Constraints

• 1 <= length of transmission <= 100
• 1 <= length of passphrase <= 100
• Both strings contain only lowercase English letters ('a'-'z').

ababab
ab

3

xyzxyzxamn
xyz

2