問題文

$N$ 人のプレイヤーがいます。初め、人 $i$ は文字列 $S_i$ を持っています。それぞれのプレイヤーは誰がどのような文字列を持っているかを全て知っています。

次の2つの段階からなるゲームを行います。

段階1

• それぞれのプレイヤーが好きな正整数を宣言する
• 宣言された正整数のうち最小のものを $K$ とする

段階2

• それぞれのプレイヤー $i$ が丁度 $K$ 回次の操作を行う
  • 自分が持っている文字列 $S_i$ の異なる位置の2文字を選択し、入れ替える

最終的に作られた文字列のうち、辞書順で最小の文字列を持っていた人全員が勝ちです。また、勝者は勝者の人数を $X$ として $N+1-X$ 点が得られます。

全員が自身の得点を最大化する戦略をとったとき、全員の得点を求めてください。

制約

• $N \ge 2$
• $2 \le |S_i| \le 10^5$
• $\sum |S_i| \le 2 \times 10^5$
• $S_i$は英小文字のみからなる

入力

入力は以下の形式で標準入力から与えられる。

$N$
$S_1$
$\vdots$
$S_N$

出力

$N$ 行出力せよ。 $i$ 行目には全員が自身の得点を最大化する戦略をとったときのプレイヤー $i$ の得点を出力せよ。

サンプル

3
ac
re
wa

0
0
3

4
abc
cba
bac
abc

0
3
3
0

5
apple
banana
cabbage
dragonfruit
egg

0
0
5
0
0