Cho bàn cờ kích thước ~m×n~ chứa các số nguyên và ~q~ quân mã rải rác trên bàn cờ. Các dòng trên bàn cờ được đánh số từ 1 đến ~m~, các cột từ 1 đến ~n~.

Đếm xem, trong một lần di chuyển, mỗi quân mã có thể di chuyển đến bao nhiêu ô có giá trị là số nguyên tố trong bàn cờ.

Dữ liệu

• Dòng đầu chứa 3 số nguyên ~m, n, q~. ~(m, n, q \le 100)~
• ~m~ dòng tiếp theo, mỗi dòng chứa ~n~ phần tử là giá trị của bảng. Các giá trị không quá ~10^4~
• ~q~ dòng cuối cùng, mỗi dòng chứa cặp chỉ số của quân mã thứ ~i~ (~1 \le i \le q~).

Kết quả

Gồm ~q~ dòng, tương ứng câu trả lời cho từng quân mã.

Input

3 3 2
4 3 8 
8 8 2 
3 9 3 
1 2
3 3

Output

2
1