### 问题描述

小明给了一个只有 $0$ 和 $1$ 组成的邻接矩阵 $a$，矩阵 $a$ 的大小为 $n\times n$，$a_{i,j}=1$ 表示 $i$ 到 $j$ 有一条有向边长度为 $1$ 的边。现在他将 $k^2$ 个矩阵 $a$ 平铺到一个 $nk \times nk$ 的矩阵 $b$ 中，邻接矩阵 $b$ 表示图 $G$ 的边的情况。

他给了你 $q$ 个询问，每个询问包含图 $G$ 中的两个点 $x_i,y_i$，他想问问有多少个询问 $x_i$ 到 $y_i$ 的最小距离小于等于 $m$。

若无法到达，则不计入答案。

注意：点的坐标从 $1$ 开始，不是 $0$。

输入格式

第一行包含四个整数 $n,k,q,m$，其中分别表示矩阵 $a$ 的点的个数，矩阵 $b$ 有 $k^2$ 个矩阵 $a$，询问的个数，小明所要求的最大距离。

接下来 $n$ 行，每行 $n$ 个整数，表示矩阵 $a$。

接下来 $q$ 行，每行两个整数 $x_i,y_i$，分别表示在图 $G$ 中的起点和终点。

保证 $a_{i,j}$ 只为 $0$ 或 $1$。

输出格式

输出共 $1$ 行，包含一个整数，有多少个询问 $x_i$ 到 $y_i$ 的最小距离小于等于 $m$。

样例输入

3 2 4 2
1 1 1
1 1 0
0 1 0
1 2
1 4
1 6
6 3

样例输出

3

评测数据规模

$1 \leq n,q\leq 100$，$1\leq k\leq 10^9$，$0\leq m \leq 10^{15}$，$1\leq x_i,y_i\leq n\times k$。