Background

The testdata on Luogu is only for community exchange and is not official testdata. Official judging link: https://www.cspro.org/.

Problem Description

In a chess game, if the same position occurs 3 times or more, consecutively or intermittently, either side may claim a draw.

Each chess position can be represented by an $8 \times 8$ character array, where each entry corresponds to a square on the board. The six types of pieces king, queen, rook, bishop, knight, and pawn are represented by the letters k, q, r, b, n, p, where uppercase letters represent White and lowercase letters represent Black. Empty squares are represented by the character *. If every entry of two character arrays is identical, then they represent the same position.

Now, the positions after each move have been recorded in the above format. Please count, for each position, which occurrence number it is.

:::align{center} :::

Input Format

Read from standard input.

The first line contains a positive integer $n$, indicating that the game has a total of $n$ moves.

Then follow $8 \times n$ lines, giving in order the positions after move $1$ to move $n$. Specifically, each line contains a string of length $8$. Every 8 lines (64 characters in total) correspond to one position.

Output Format

Write to standard output.

Output $n$ lines. Each line contains an integer indicating which occurrence number this position is.

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******
****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

Hint

Sample Explanation

The positions after moves $6$ and $7$ are the same as the positions after moves $2$ and $3$, respectively. The position after move $8$ corresponds to the figure above.

Subtasks

The input satisfies $n \le 100$.

Notes

Determining repeated positions only involves string comparison. There is no need to consider the actual chess rules for making moves.

Translated by ChatGPT 5