Background

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

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

土拨鼠久久找来了一块 $n×n$ 的棋盘，上面有 $m$ 个敌方小兵，坐标分别为$(k_i,k_j)$$（1\leq k_i,k_j\leq n$。其中，棋盘的左上角为 (1,1)(1,1) 坐标。

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

Description

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

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

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

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

Format

Input

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

Output

One integer, the sum of x and y.

Samples

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

8
6

样例解释1

对于位置处于 $(2,2)$ 的皇后，可以攻击到棋盘中所有小兵，所以答案输出 $8$。

对于位置处于 $(2,1)$ 的皇后，可以攻击到位置处于 $(1,1),(1,2),(2,1),(2,3),(3,1),(3,2)$ 的小兵，答案输出 $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

Limitation

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

对于 $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$。