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

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

Примеры