邻居们又在找谢别克的麻烦，并给他想出了新的挑战。这次他们有一段长度为 的线段。邻居们把谢别克放在了坐标 处，并要求他跳到坐标为 的点。
但谢别克有个问题。他只能向前跳跃长度 、 或 。然而邻居们决定进一步限制他。他们给了他一个长度为 、由小写拉丁字母组成的字符串 。谢别克可以向前跳跃长度 ()，当且仅当在字符串 中存在一个子串，满足以下条件：
- 该子串的长度为 。
- 子串中的所有字母都相同。
- 在子串的左侧，要么是一个不同于子串字母的字符，要么不存在任何字符（即子串位于字符串边缘）。
- 在子串的右侧，要么是一个不同于子串字母的字符，要么不存在任何字符。
如果字符串 可以通过从 的开头删除若干个（可以是零个或全部）字符，并从结尾删除若干个（可以是零个或全部）字符得到，则称 是 的子串。
例如，假设字符串为 aabaaabbcbbbebbab 且 。那么该字符串中有多个子串符合限制条件：(aa)baaa(bb)cbbbe(bb)ab。因此在这种情况下，可以跳跃长度为 。此外，该字符串也允许跳跃长度为 和 。而字符串 ebbbcedddd 只允许跳跃长度 和 。
谢别克需要仅使用允许的跳跃长度，从点 跳到坐标为 的点，并且使用最少的跳跃次数。假设你就是谢别克，请计算这个最少的跳跃次数。
请注意，谢别克需要恰好跳到坐标为 的点，而不是 或 。
