Problem Statement

There are $N(N+1)/2$ balls arranged in an $N$-tiered pyramid as shown in the figure below. Let $(0, 0)$ be the coordinates of the ball at the top of the pyramid, and let $(x,y)$ be the coordinates of the $y (0\\leq y\\leq x)$-th ball from the left in the $x (0\\leq x-1)$-th tier from the top.

Each ball is labeled with a number from $0$ to $N(N+1)/2-1$, and the numbers on each ball are all different. You can swap two adjacent balls in six directions in a single operation. Here, the balls at coordinates $(x_1,y_1)$ and $(x_2,y_2)$ are adjacent in six directions if one of the following conditions is satisfied.

• $x_1=x_2-1$ and $y_1=y_2-1$
• $x_1=x_2-1$ and $y_1=y_2$
• $x_1=x_2$ and $y_1=y_2-1$
• $x_1=x_2$ and $y_1=y_2+1$
• $x_1=x_2+1$ and $y_1=y_2$
• $x_1=x_2+1$ and $y_1=y_2+1$

By performing this operation at most $10000$ times, please arrange the balls so that every ball $(x,y) (0\\leq x\\leq N-2, 0\\leq y\\leq x)$ except those in the lowest tier has a smaller number than the two balls $(x+1,y), (x+1,y+1)$ directly below it. Please achieve this with as few operations as possible.

Scoring

Let $K$ be the number of operations and $E$ be the number of pairs of balls violating the condition after finishing the operations. Here $E$ is the total number of pairs of $(x,y)$ and $(x+1,y') (y'\\in\\{y,y+1\\})$ such that the ball $(x,y)$ has a larger number than the ball $(x+1,y')$. Then you will obtain the following score.

• If $E=0$, $100000-5K$.
• If $E>0$, $50000-50E$.

There are 150 test cases, and the score of a submission is the total score for each test case. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA