Задача Shift. Дано рядок S та рядок А. Необхідно знайти циклічний зсув рядка S з максимальною кількістю входжень в нього рядка А  і вивести не сам циклічний зсув, а саме максимальну кількість входжень серед усіх зсувів. Наприклад, якщо в рядку ABCDA шукати входження рядка АА, то максимальна кількість входжень дорівнює 1 (в зсувах  AABCD чи BCDAA). У рядках гарантовано відсутні пропуски ("пробіли").

Технічні умови. Програма Shift читає з пристрою стандартного введення рядок символів S, а в другому – підрядок А. Довжина кожного рядка не перевищує 10⁶. Програма виводить на пристрій стандартного виведення єдине число – шукану величину.

Приклади