Cuộc chiến tập đoàn

Cho hai xâu $s$ và $t$ chỉ gồm các chữ cái latinh thường. Trong xâu $s$, bạn được phép thay thế một số ký tự bằng dấu #. Hãy tìm số lượng ký tự ít nhất cần thay sao cho sau khi thay, xâu $t$ không còn xuất hiện trong $s$ với vai trò một xâu con liên tiếp.

Dữ liệu vào

• Dòng đầu chứa xâu $s$.
• Dòng thứ hai chứa xâu $t$.

Dữ liệu ra

In ra một số nguyên duy nhất — số ký tự ít nhất cần thay bằng #.

Ràng buộc

• $1\le |s|\le {10}^5$
• $1\le |t|\le 30$
• Cả hai xâu chỉ gồm các chữ cái latinh thường.

Ví dụ