问题描述

国际象棋在对局时，如果同一局面连续或间断出现 $3$ 次或更多次，任意一方都可以提出和棋。每一个局面可以用一个 $8\times8$ 的字符矩阵表示，每个字符对应棋盘上的一个格子：

• 六种棋子国王、后、车、象、马、兵分别用字母 $k,q,r,b,n,p$ 表示，大写字母表示白方，小写字母表示黑方。
• 棋盘上无棋子的位置用字符 * 表示。

若两个 $8\times8$ 字符矩阵在每个位置上字符都相同，则认为它们表示相同的局面。现已按照上述方式整理好了每一步棋后的局面（每一步给出一个 $8\times8$ 的字符矩阵），请统计并输出每个局面是该局面出现的第几次。

注意：判断重复局面只需做字符串比较，不需要考虑国际象棋的行棋规则或走法合法性。

输入格式

• 第一行包含一个正整数 $n$，表示这盘棋总共有 $n$ 步。（$1 \le n \le 100$）。
• 接下来共有 $8\times n$ 行，每 $8$ 行描述一个局面（第 $1$ 到第 $n$ 步后的局面）。每行是一个长度为 $8$ 的字符串，字符集仅包含 k,q,r,b,n,p（大小写混合）和 *。

即第 $1$ 个局面的 $8$ 行先给出，第 $2$ 个局面的 $8$ 行随后给出，依此类推，共 $8n$ 行。

输出格式

输出共 $n$ 行。第 $i$ 行输出一个整数，表示第 $i$ 步后的局面是该局面出现的第几次（从 $1$ 开始计数）。

数据范围

输入样例

8
********
******pk
*****r*p
p*pQ****
********
**b*B*PP
****qP**
**R***K*
********
******pk
*****r*p
p*pQ****
*b******
****B*PP
****qP**
**R***K*
********
******pk
*****r*p
p*p*****
*b**Q***
****B*PP
****qP**
**R***K*
******k*
******p*
*****r*p
p*p*****
*b**Q***
****B*PP
****qP**
**R***K*
******k*
******p*
*****r*p
p*pQ*****
*b**Q***
****B*PP
****qP**
**R***K*
********
******pk
*****r*p
p*pQ****
*b******
****B*PP
****qP**
**R***K*
********
******pk
*****r*p
p*p*****
*b**Q***
****B*PP
****qP**
**R***K*
********
******pk
******rp
p*p*****
*b**Q***
****B*PP
****qP**
**R***K*

输出样例

1
1
1
1
1
2
2
1

说明

样例解释

样例中第 $6$、$7$ 步后的局面分别与第 $2$、$3$ 步后的局面相同，因此第 $6$、$7$ 步输出 $2$。第 $8$ 步的局面与给出的图相对应，且在之前未出现过，故输出 $1$。