小藍(lán)很喜歡 owo ，他現(xiàn)在有一些字符串，他想將這些字符串拼接起來，使得最終得到的字符串中出現(xiàn)盡可能多的 owo 。

在計(jì)算數(shù)量時(shí)，允許字符重疊，即 owowo 計(jì)算為 2 個(gè)，owowowo 計(jì)算為 3 個(gè)。

請(qǐng)算出最優(yōu)情況下得到的字符串中有多少個(gè) owo。

輸入的第一行包含一個(gè)整數(shù) n ，表示小藍(lán)擁有的字符串的數(shù)量。

接下來 n 行，每行包含一個(gè)由小寫英文字母組成的字符串 s_i 。

輸出 n 行，每行包含一個(gè)整數(shù)，表示前 i 個(gè)字符串在最優(yōu)拼接方案中可以得到的 owo 的數(shù)量。

3
owo
w
ow

1
1
2

對(duì)于 10% 的評(píng)測(cè)用例，n ≤ 10；

對(duì)于 40% 的評(píng)測(cè)用例，n ≤ 300；

對(duì)于 60% 的評(píng)測(cè)用例，n ≤ 5000；

對(duì)于所有評(píng)測(cè)用例，1 ≤ n ≤ 10⁶ ，1 ≤ |s_i | ， ∑ |s_i | ≤ 10⁶，其中 |s_i | 表示字符串 s_i 的長度。

本試題適用于用c/c++/java代碼來完成，如用Python代碼出現(xiàn)時(shí)間超限問題建議轉(zhuǎn)到：http://www.sztianhecheng.cn/oj/problem.php?id=2738鏈接