Description

围棋是一种源远流长的策略性棋类游戏，起源于中国，至今已有超过2500年的历史。标准棋盘由19×19条线交织成361个交叉点，棋子落在这些点上。初学者也可能使用较小的9×9或13×13棋盘练习。棋子分为黑白两色，双方轮流落子，黑方先行（现代比赛通常采用贴目规则平衡先手优势）。通过围地（占据空地）和围杀对手棋子，最终占据更多区域的一方获胜。气：棋子相邻的空白交叉点称为“气”。当一颗棋子或相连的棋子群所有气被对方占据，则被“提子”（移除棋盘）。眼：棋子围成的空白交叉点。拥有两个独立“眼”的棋子群不可被提，称为“活棋”。劫争：特殊规则防止无限循环提子，一方提劫后，对手需隔一手才能回提。中国规则（数子法）：计算活子+围地总和，黑方需贴3又3/4子（约7.5目）以平衡先手优势。日本规则（数目法）：仅计算围地+提子数，黑方贴6.5目。终局条件为双方均无可行着法，或连续弃权（Pass）。围棋在中国古代位列“琴棋书画”四艺之一，被誉为“手谈”，强调思维交锋与战略艺术。传播至日韩后成为重要文化符号，职业棋手制度在日本尤为成熟，催生了吴清源、李昌镐等传奇人物。

但是围棋对 LargeRice16pro 还是太难了一点，有没有更简单适合一点的推荐？

有的，有的，像这样的棋类还有 9 个。

五子棋是一种两人对弈的简版连珠棋类，规则简单却富含策略。棋盘通常为15×15网格，双方执黑白子轮流落子，率先在横、竖、斜任一方向连成五子者胜。为避免先手优势，竞技规则引入“禁手”（如黑棋禁止双活三、四三三等），平衡胜负概率。其战术核心在于攻防转换，需预判对手意图，同时构造“活四”“冲四”等必胜阵型。与围棋的围地思维不同，五子棋更侧重快速连线与精准计算，适合快节奏脑力对决，兼具休闲性与竞技深度。

五子棋简单来说说就是当在横、竖、斜上有不少于 5 颗同色棋子时游戏结束，执该棋子者获胜。

现在 LargeRice16pro 想学习一下五子棋，所以请你帮助他完成以下任务：

给定一个棋盘，黑棋先手，白棋后手，求有多少个子矩阵满足对于当前局面存在后手必胜策略。

为了简化问题，假设黑白地位等价，不考虑“禁手”。仅需要考虑是否能够形成横、竖、斜的五个同色即可。

Format

Input

第一行一个正整数 $n$ 表示棋盘大小。

接下来 $n$ 行，每行 $n$ 个数字表示棋盘局面，$1$ 表示白棋，$0$ 表示黑棋，$2$ 表示空。

Output

输出一行一个整数表示对于当前局面存在后手必胜策略的子矩阵数量。

Samples

1 0 1 0 1 0 0 1 2 0 1 1 2 0 2
0 0 0 2 1 2 2 0 1 0 0 2 1 0 2
1 0 0 2 1 0 0 2 0 1 0 0 1 0 1
0 2 1 1 0 2 2 2 2 0 0 2 2 2 1
2 0 1 2 2 0 2 2 0 1 2 0 0 0 0
2 1 1 0 0 2 0 0 1 1 0 2 2 1 2
0 1 2 2 2 1 2 2 2 2 1 1 2 0 0
0 0 2 0 2 2 1 1 2 0 1 0 2 1 1
0 0 2 0 1 2 2 2 1 2 2 2 2 2 1
2 2 1 1 0 2 0 2 1 2 1 2 2 1 2
1 2 2 1 2 2 0 1 2 1 1 2 0 2 0
0 0 2 2 1 2 1 0 0 2 2 0 0 0 0
0 2 1 1 1 2 0 0 0 1 1 0 0 1 2
2 2 2 0 1 0 1 0 1 0 0 0 2 0 0
1 0 1 1 0 1 1 2 1 1 1 2 2 2 1

293