4601 - NOIP 2021 提高第四题棋局（chess）

通过次数

提交次数

旧版界面

Time Limit : 1 秒

Memory Limit : 512 MB

在输了一晚上的麻将之后，小 z 和小 c 卸掉了手机上的所有牌类游戏。不过这怎么可能阻挡得了他们上课颓废的决心呢？现在他们的目光盯在了棋类游戏上，但他们两个除了天天下飞行器以外，几乎所有棋类游戏都只懂个大概规则。“既然我们都会玩但只能玩一点点，不如我们自己搞个缝合怪出来吧！” 于是，在他们的精心脑洞之下，一个融合了围棋、象棋与军棋的奇妙游戏诞生了……

Input

Output

对于每组数据输出 q 行，每行一个非负整数，表示第 i 枚棋子放置后能走到的交叉点数量。

Examples

Input

Output

Input

Output

Hint

【样例 1 解释】放置棋子 1 后，它能走到的位置为 (2, 1),(2, 2),(3, 2),(3, 3) 。放置棋子 2 后，它能走到的位置为 (2, 2),(2, 3),(3, 1) 。放置棋子 3 后，它能走到的位置为 (1, 1),(1, 3),(2, 2) 。放置棋子 4 后，它能走到的位置为 (2, 2),(3, 1),(3, 3) 。放置棋子 5 后，它能走到的位置为 (2, 3),(3, 2) 。