Давным-давно в далёкой-далёкой галактике противоборствовали две огромные IT-корпорации: Pineapple и Gogol. Противостояние длится уже многие годы, но близится переломный момент: компания Gogol разработала абсолютно новое устройство, не имеющее аналогов — планшет Lastus 3000.

В этом устройстве используется впервые созданный искусственный интеллект (ИИ). Члены компании Pineapple пытались всеми силами отложить выход нового девайса. В конце концов, за неделю до выхода Lastus 3000 на рынок юристы обнаружили, что название искусственного интеллекта очень похоже на название телефона, который выпустила компания Pineapple 200 лет назад. Так как компания Pinapple обладает авторским правом на это название, она потребовала изменить имя искусственного интеллекта.

Pineapple утверждает, что название их телефона присутствует в качестве подстроки в имени ИИ. Название этой технологии уже было выгравировано на всех планшетах, поэтому директор Gogol предложил вместо некоторых букв в названии ИИ поставить символ «#». Так как это довольно затратно, надо найти минимальное количество символов, которые нужно заменить на «#», чтобы имя ИИ больше не содержало название телефона Pineapple в качестве подстроки. Помогите компании Gogol решить эту задачу.

Подстрокой называется непустая последовательность подряд идущих символов строки.