暂无测试数据。

国际象棋，是一款风靡全球的棋盘游戏，棋盘为一个 $n\times n$ 的矩阵。

国际象棋中实力最强的棋子为皇后，蒜头君最喜欢皇后，皇后可以上下左右对角线走（对角线有两条，从左上到右下和从右上到左下），且移动距离不限。因为蒜头君过于偏爱皇后，蒜头君制定了一条新的规则，那就是所有与皇后在同一横线、同一竖线、同一对角线（两条对角线）的敌方小兵都可以被皇后攻击。

蒜头君找来了一块 $n\times n$ 的棋盘，上面有 $m$ 个敌方小兵，坐标分别为 $(k_i,k_j)$（$1\leq k_i,k_j\leq n$）。其中，棋盘的左上角为 $(1,1)$ 坐标。

现在，蒜头君想知道，在他制定的规则下，对于一个坐标为 $(i,j)$ 的皇后能够攻击到的小兵数量是多少。

输入格式

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

接下来 $n$ 行，每行输入 $n$ 个数，用来表示在当前位置有没有小兵，$0$ 表示当前位置没有小兵，$1$ 表示当前位置存在一个小兵。

接下来一个输入一个正整数 $q$，表示接下来询问对于 $q$ 个皇后。

接下来 $q$ 行，每行输入两个正整数 $(i,j)$，表示当前询问的皇后的位置。

输出格式

输出共 $q$ 行，每行输出一个整数，表示对于当前棋局，每个皇后分别能攻击到多少个小兵。

数据范围

数据不保证皇后所摆放的位置没有士兵。

对于 $10\%$ 的数据，有 $2\leq n\leq 10, 1\leq q\leq 10$。

对于另外 $20\%$ 的数据，有 $2\leq n\leq 100, 1\leq q\leq 100$。

对于另外 $20\%$ 的数据，有 $2\leq n\leq 10^3, q=1$。

对于 $100\%$ 的数据，有 $2\leq n\leq 10^3, 1\leq q\leq 10^5$。

3
1 1 1
1 0 1
1 1 1
2
2 2
2 1

8
6

4
1 0 1 0
0 1 0 1
1 0 1 0
0 1 0 1
2
1 1
4 2

6
6