Kiến

Trên lưới nguyên (mỗi giao điểm có tọa độ nguyên $(x,y)$), người ta đặt một đàn kiến. Kiến di chuyển theo quy tắc sau: cứ mỗi phút, tại mỗi giao điểm $(x,y)$ đang có ít nhất 4 con kiến, sẽ có một nhóm gồm đúng 4 con tách ra và bò sang 4 giao điểm kề cạnh, mỗi hướng một con: $(x+1,y)$, $(x-1,y)$, $(x,y+1)$, $(x,y-1)$. Ngoài quá trình này không có di chuyển nào khác xảy ra.

Ban đầu người ta đặt $n$ con kiến vào giao điểm $(0,0)$. Quá trình trên diễn ra cho đến khi không còn giao điểm nào chứa từ 4 con kiến trở lên, khi đó đàn kiến ngừng di chuyển. Trạng thái dừng cuối cùng là duy nhất, không phụ thuộc thứ tự thực hiện các bước tách.

Cho $t$ truy vấn, mỗi truy vấn là một giao điểm $(x_i,y_i)$. Hãy cho biết số kiến tại giao điểm đó khi đàn kiến đã ngừng di chuyển.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $t$.
• $t$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_i$, $y_i$ là tọa độ giao điểm cần truy vấn. Các truy vấn có thể trùng nhau.

Dữ liệu ra

In ra $t$ dòng, mỗi dòng một số nguyên là số kiến tại giao điểm tương ứng ở trạng thái dừng.

Ràng buộc

• $0\le n\le 30000$
• $1\le t\le 50000$
• $-{10}^9\le x_i,y_i\le {10}^9$

Ví dụ