### 问题描述 小明给了一个只有 $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$。 ### 样例输入 ```text 3 2 4 2 1 1 1 1 1 0 0 1 0 1 2 1 4 1 6 6 3 ``` ### 样例输出 ```text 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$。