### 问题描述 每逢七夕，牛郎织女都会在鹊桥上相会。为了增添节日气氛，王母娘娘决定借鉴这一浪漫传统，在天庭举办一场别开生面的“花魁大赛”。 比赛共有 $n$ 位仙女参加比赛。每位仙女都准备了一串花环，花环可以看作是一个字符串，字符串上的每个字符都表示花环中的一朵花。由于仙女们心灵纯净，彼此之间毫无秘密，因此每位仙女都知道其他仙女的花环是什么样的。 比赛的规则如下：每位仙女需要确定她们心目中鹊桥的适宜长度（长度为正整数），并将这个长度告知织女。织女会从所有仙女所提供的长度中选取最短的作为鹊桥的最终长度（记为 $m$）来搭建鹊桥。在鹊桥搭建完成之后，每位仙女都必须对自己的花环进行 $m$ 次调整。每次调整，可以选择花环中两个不同位置的花朵，并交换它们的位置。待所有仙女都调整完后，拥有字典序最小的花环的仙女将赢得比赛，成为今年的“花魁”（如果有多个仙女都拥有字典序最小的花环，那么她们将共同分享“花魁”的称号）。 已知所有仙女都想要成为“花魁”，并且都会采用最优策略。那么请问，在这种情况下，会有多少仙女成为“花魁”？ 每位仙女希望在自己成为花魁的前提下，共享花魁称号的仙女尽可能少。 ### 输入格式 第一行包含一个整数 $n$（$2 \leq n \leq 10^5$），表示参加比赛的仙女数量。 接下来 $n$ 行，每行包含一个长度在 $2 \sim 10^5$ 之间、仅由小写字符构成的字符串 $S$，表示仙女们的花环。 数据保证输入的字符串总长度不超过 $10^6$。 ### 输出格式 输出一个整数，分别表示“花魁”的数量。 ### 样例输入 ```text 3 abc acb bac ``` ### 样例输出 ```text 2 ``` ### 样例说明 在最优方案下，第二位仙女和第三位仙女选择的长度可以是 $1$。由于 $1$ 是最小的正整数，因此无论第一位仙女选择的长度为多少，$m$ 都必定为 $1$。 在必须进行 $1$ 次调整的情况下： - 第一位仙女可以将 $abc$ 中的 $b$ 和 $c$ 交换，得到 $acb$。 - 第二位仙女可以将 $acb$ 中的 $b$ 和 $c$ 交换，得到 $abc$。 - 第三位仙女可以将 $bac$ 中的 $b$ 和 $a$ 交换，得到 $abc$。 第二位仙女、第三位仙女将成为“花魁”，“花魁”的总数为 $2$。