Appleman 和 Toastman 喜欢游戏。他们今天玩了一个跟字符串有关的游戏，其规则如下：首先 Toastman 给出两个字符串 $s$ 和 $t$（仅由 A，B，C，D 构成），然后 Appleman 必须尽可能快地用 $t$ 的子串构成 $s$。开始时 Appleman 有一个空字符串，他每秒钟可以将 $t$ 的一个子串接在这个字符串的后面。

现在游戏开始了，Toastman 已经给出了 $t$，但他还没想好 $s$，Toastman 想给出一个长度为 $n$，并且使得 Appleman 用时最长的 $s$。请你告诉 Toastman，对于这样的 $s$，Appleman 的最短用时是多久。

Appleman 和 Toastman 喜欢游戏。他们今天玩了一个跟字符串有关的游戏，其规则如下：首先 Toastman 给出两个字符串 $s$ 和 $t$（仅由 `A`，`B`，`C`，`D` 构成），然后 Appleman 必须尽可能快地用 $t$ 的子串构成 $s$。开始时 Appleman 有一个空字符串，他每秒钟可以将 $t$ 的一个子串接在这个字符串的后面。

现在游戏开始了，Toastman 已经给出了 $t$，但他还没想好 $s$，Toastman 想给出一个长度为 $n$，并且使得 Appleman 用时最长的 $s$。请你告诉 Toastman，对于这样的 $s$，Appleman 的最短用时是多久。

简要版：

给定一个串 $t$，由 A，B，C，D 四种字符构成且每种字符至少出现一次。有一个空串，每次可以选 $t$ 的一个子串加在它后面。求一个长度为 $n$ 字符集为 ABCD 的串 $s$，最大化以上述操作得到 $s$ 的最小操作次数，输出这个最大值。

给定一个串 $t$，由 `A`，`B`，`C`，`D` 四种字符构成且每种字符至少出现一次。有一个空串，每次可以选 $t$ 的一个子串加在它后面。求一个长度为 $n$ 字符集为 `ABCD` 的串 $s$，最大化以上述操作得到 $s$ 的最小操作次数，输出这个最大值。