Acesrc 是一位天才作曲家。他喜欢创作悦耳动听的歌曲。他创作的每一首歌曲都可以看作是一个音符序列，每个音符代表声音的音高和持续时间。在本题中，我们仅考虑以下七种基本音高：

do re mi fa sol la si

每个音符的持续时间为一个单位时间。因此，总共只有七种类型的音符，我们可以用音名来表示一个音符。

Acesrc 按照以下方式创作歌曲：初始时，音符序列为空。每天，他会在序列的开头或结尾插入一个新的音符，直到歌曲创作完成。

Acesrc 特别喜欢带有重复的歌曲。对于一首包含 $n$ 个音符的歌曲，如果这首歌曲可以被划分为一个或多个长度为 $k$ ($1 \le k \le n$) 的相同片段，且后面可能跟有一个不完整的片段（该片段是完整片段的前缀），我们就称这首歌曲具有长度为 $k$ 的重复。例如，do re do re do 可以划分为 do re | do re | do，因此它具有长度为 2 的重复；类似地，do re mi do re mi 具有长度为 3 的重复，而 do re do re mi 具有长度为 5 的重复。

Acesrc 想知道，在他每天添加一个音符后，这首歌曲所具有的重复长度的种类数。你能帮帮他吗？

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示 Acesrc 创作歌曲的天数。 接下来的 $n$ 行中，第 $i$ 行包含一个字符 $a$ ($a \in \{p, a\}$)（其中 p 表示 prepend，即在开头插入；a 表示 append，即在结尾插入）和一个字符串 $s$ ($s \in \{\text{do, re, mi, fa, sol, la, si}\}$)，表示 Acesrc 在第 $i$ 天采取的行动。

输出格式

输出 $n$ 行。第 $i$ 行应为一个整数，表示第 $i$ 天的答案。

样例

样例输入 1

5
a do
p re
a re
a do
p do

样例输出 1

1
1
2
2
3

样例输入 2

5
a re
a do
a re
p do
a mi

样例输出 2

1
1
2
2
1