Cho bảng hình chữ nhật có $N$ hàng $M$ cột và một số nguyên dương $K$. Số nằm ở hàng $i$ cột $j$ có tọa độ là $(i, j)$ và giá trị $A_{i, j}$. Một con robot đang đứng ở vị trí $(1, 1)$ và cần di chuyển đến ô $(N, M)$. Khi đứng ở ô $(i, j)$ robot chỉ có thể di chuyển vào ba ô $(i, j + 1), (i + 1, j), (i + 1, j + 1)$.

Cho $Q$ truy vấn, mỗi truy vấn gồm một số tự nhiên $X$ $(X < K)$. Với mỗi truy vấn, hãy cho biết đường đi của robot từ ô $(1, 1)$ đến ô $(M, N)$ có thể đi qua nhiều nhất bao nhiêu ô $(i, j)$ thỏa mãn $A_{i, j} \mod K = X$.

Yêu cầu: Hãy trả lời $Q$ truy vấn của đề bài.

3 4 2 6
1 1 1 7
2 8 9 1
1 3 4 2
1
2

5
3