Dina 和 Dima 是年轻的考古学家，正在多瑙河三角洲（现代多布罗加地区）探索一个被认为属于达契亚文化（据推测是国王德塞巴鲁斯本人）的古老马赛克楼梯。

每一级台阶都由 8 块马赛克拼贴而成，每块马赛克要么是白色，要么是红色。每天早晨，他们都会挖出楼梯的恰好一级台阶，显然是从上到下依次进行。

每天下午，在吃过午饭走下楼梯前往工作区域时，他们都会玩一个游戏。他们会（非常小心地）把一块手帕放在最顶端的台阶上。然后他们轮流进行操作，由 Dina 先手。每次操作中，玩家需要将手帕向下移动几级台阶。只有当两级台阶之间的距离小于或等于它们相同马赛克块的数量（即在相同位置上颜色相同的马赛克对数）时，才允许将手帕从一级台阶移动到更低的一级台阶。无法进行操作的玩家输掉今天的游戏。

例如，在下图中，Dina 可以将手帕从最顶端的台阶移动到中间的台阶（因为 $1 \le 7$）或者移动到最底端的台阶（因为 $2 \le 6$）。

对于每个下午，求出如果两人都采取最优策略，谁将赢得游戏。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 300\,000$) —— 楼梯的高度。

接下来的 $n$ 行，每行包含 8 个字符 'W' 或 'R' —— 从上到下依次描述每级台阶的马赛克颜色。

输出格式

输出一行，包含 $n$ 个数字，每个数字对应一个下午的游戏结果。1 表示 Dina 获胜，2 表示 Dima 获胜。

样例

输入样例 1

3
WWWWWWWW
RRRRRRRR
WWWWWWWW

输出样例 1

221

输入样例 2

7
WWWWRRWW
WWWRRRWW
WWWRRWWW
WWRRRWWW
WWRRWWWW
WRRRWWWW
WRRWWWWW

输出样例 2

2111121