SD有一名神犇叫做Oxer，他觉得字符串的题目都太水了，于是便出了一道题来虐蒟蒻yts1999。

他给出了一个字符串T，字符串T中有且仅有 $4$ 种字符 'A', 'B', 'C', 'D'。现在他要求蒟蒻yts1999构造一个新的字符串 $S$，构造的方法是：进行多次操作，每一次操作选择 $T$ 的一个子串，将其加入 $S$ 的末尾。

对于一个可构造出的字符串 $S$，可能有多种构造方案，Oxer定义构造字符串S所需的操作次数为所有构造方案中操作次数的最小值。

Oxer想知道对于给定的正整数 $N$ 和字符串 $T$，他所能构造出的所有长度为 $N$ 的字符串 $S$ 中，构造所需的操作次数最大的字符串的操作次数。

第一行包含一个整数 $N$，表示要构造的字符串长度。

第二行包含一个字符串 $T$，$T$ 的意义如题所述。