It has been noted that if some ants are put in the junctions of the graphene integer lattice then they will act in the following fashion: every minute at each junction (x, y) containing at least four ants a group of four ants will be formed, and these four ants will scatter to the neighbouring junctions (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1) — one ant in each direction. No other ant movements will happen. Ants never interfere with each other.

Scientists have put a colony of n ants into the junction (0, 0) and now they wish to know how many ants will there be at some given junctions, when the movement of the ants stops.

Input

First input line contains integers n (0 ≤ n ≤ 30000) and t (1 ≤ t ≤ 50000), where n is the number of ants in the colony and t is the number of queries. Each of the next t lines contains coordinates of a query junction: integers xi, yi ( - 109 ≤ xi, yi ≤ 109). Queries may coincide.

It is guaranteed that there will be a certain moment of time when no possible movements can happen (in other words, the process will eventually end).

Output

Print t integers, one per line — the number of ants at the corresponding junctions when the movement of the ants stops.

Examples

Input

1 3
0 1
0 0
0 -1


Output

0
1
0


Input

6 5
0 -2
0 -1
0 0
0 1
0 2


Output

0
1
2
1
0

Note

In the first sample the colony consists of the one ant, so nothing happens at all.

In the second sample the colony consists of 6 ants. At the first minute 4 ants scatter from (0, 0) to the neighbouring junctions. After that the process stops.
203 30
-3 3
-3 10
-7 -6
1 8
-5 2
-9 10
-6 4
8 2
-2 -5
-3 2
1 6
-6 -9
10 9
-3 -9
-7 5
3 8
1 -4
-4 -5
-2 1
-6 -10
10 10
4 -1
0 -2
9 9
-5 6
-9 -5
7 -10
-6 3
-3 -4
9 -4
 25965 53
-1 -2
1 5
0 3
4 4
-3 -2
5 4
-3 -4
-4 3
1 -5
2 -5
0 4
-1 -1
-3 -2
1 -5
-1 5
2 -1
-5 -2
-5 -4
4 -2
2 -5
3 -3
-5 4
-4 0
3 0
-2 4
2 1
5 -3
-1 0
4 -2
0 -4
-5 0
4 4
-5 -2
-1 -3
2 -5
1 -3
-4 3
4 1
3 2
-5 -3
-1 0
1 -1
-2 2
5 -2
4 0
-3 4
4 -1
0 5
0 5
-5 -5
-3 -2
3 4
-2 -3
 26306 12
-209686696 -252039951
336170474 874855458
967313882 301142304
-945290114 -298685345
260111651 -646079544
-482524885 -594243108
455231664 272297143
480331417 -948955565
-625406827 630428708
-387747305 -363872220
803315959 -614198766
119673742 -261947378
 30000 3
0 1
0 2
0 3
 30000 10
0 0
4 0
0 4
0 0
-1000000000 999999999
4 0
0 0
-1000000000 999999999
30 -31
-31 30
 276 70
1 -9
-5 -4
1 -4
-4 5
7 10
3 -1
-10 8
7 -8
-7 5
0 4
10 9
10 2
-5 2
6 9
9 8
-6 -3
8 -3
-8 9
3 9
4 -1
7 -1
-7 0
10 1
-5 3
-4 9
-5 3
5 0
8 -7
-8 9
3 -8
-5 -1
9 9
4 3
5 4
7 7
-8 -3
5 2
-7 1
-2 2
1 1
-2 -5
-8 -9
-1 -7
5 -2
-5 8
2 -1
8 5
1 2
-10 -2
-2 -4
4 -1
10 4
-8 0
3 5
8 -10
10 6
-1 -4
3 -10
-6 10
-5 0
7 10
3 -3
10 -7
-1 7
8 -4
-4 10
-7 5
8 -9
2 -10
6 7
 253 59
8 -6
8 7
7 9
0 -9
4 2
7 -9
-3 9
-7 4
4 8
9 6
-3 -8
9 9
1 -5
-9 -9
5 3
2 10
-4 8
3 -7
1 7
9 2
9 5
10 1
9 7
1 -8
4 10
-2 3
0 6
-7 9
-6 2
-8 -8
-7 -5
-5 10
-8 8
6 -2
8 -7
-3 -8
4 -5
1 -6
-3 7
-6 6
4 -7
-6 3
-1 4
7 6
9 5
-10 -2
-4 -2
0 -9
0 2
-4 10
2 -4
2 -4
-8 10
7 4
1 2
4 7
7 -3
-2 -7
-10 -5
 15608 49
2 -5
2 -5
-3 1
1 0
-2 -5
4 1
-2 3
-2 -1
1 1
-5 -3
3 0
-2 -3
-2 -3
3 5
0 3
0 -1
-1 5
0 -5
-2 -2
4 4
-4 -1
2 1
-2 4
1 -2
-5 -2
5 3
-3 0
1 -3
-5 4
1 4
4 -2
1 2
4 -5
1 -1
3 -2
0 -4
-5 -2
4 4
-3 2
0 5
1 1
-4 1
-2 4
-1 -3
-4 5
0 -1
-3 4
1 5
4 -5
 26651 2
-107823434 -542137732
867125466 -850064178
 8 3
0 -1
0 0
0 1
 312 26
4 -2
6 5
6 3
-6 0
-1 5
-4 1
-3 -8
-2 4
-2 2
-4 7
3 -1
-8 3
10 -8
0 9
0 -4
7 1
-9 4
3 -2
-5 10
6 2
0 5
-7 0
-6 5
9 -1
-6 -7
-2 5
 28544 11
339617704 -734139583
469446397 750258071
-194215639 598429286
493177541 235545610
-770401624 534148219
884509845 -513104519
-502851919 726069608
-530085595 -961503335
-837578722 615771576
-887805545 412894108
129300206 -153569622
 0 4
0 0
0 -1000000000
1 0
0 0
 30000 39
2650 -1515
-3169 4818
-1896 2727
1323 -2335
-387 901
-4299 1481
-2114 4435
3654 -2730
4569 3801
-3815 -3355
4777 1749
4486 -780
-3936 -158
717 -3518
4765 -909
-3032 3726
-2970 3346
2067 -1560
-521 -1331
-4953 -2098
-849 580
-4941 4018
1338 -2629
-1444 -3550
1502 4995
1156 659
-4477 4062
1922 -1204
3882 -4411
2635 4895
-1602 -3199
-4098 -3015
2539 1489
-4029 1403
-705 -1612
4042 2461
1409 4157
57 -2317
-2344 2649
 30000 4
-1000000000 -1000000000
1000000000 -1000000000
-1000000000 1000000000
1000000000 1000000000
 24669 28
1 3
4 -4
-3 -4
4 4
0 -2
3 0
-5 -5
3 -5
-5 4
3 5
5 5
-5 1
0 -3
-4 2
4 3
5 -4
-4 0
3 0
4 2
-3 4
-4 3
0 -5
-1 3
-1 2
1 -5
0 5
4 -2
1 4
 25003 29
-16 21
2 -20
-23 16
22 24
-28 19
14 10
-9 9
12 3
-20 24
-26 -9
1 -10
-24 -2
25 0
19 -14
14 26
11 7
17 9
-20 -23
-12 27
5 -23
29 8
10 13
14 -10
-2 3
0 -21
16 -8
598025579 -556795415
-921724564 -156542003
-514479908 560347326

0
0
0
0
1
0
0
0
1
3
0
0
0
0
0
0
3
0
2
0
0
3
3
0
0
0
0
0
3
0
 3
0
1
2
2
1
2
2
0
2
1
2
2
0
0
3
2
1
3
2
2
1
1
1
3
3
3
3
3
1
3
2
2
3
2
3
2
2
2
3
3
2
0
2
1
2
2
3
3
0
2
2
2
 0
0
0
0
0
0
0
0
0
0
0
0
                                                                2
                                                               2
                                                               0
                                                                0
                                                               1
                                                               1
                                                               0
0
                                                               1
                                                               0
0
0
0
 0
2
3
2
0
0
0
0
0
2
0
0
2
0
0
1
0
0
0
3
0
0
0
1
0
1
3
0
0
0
1
0
3
2
0
0
2
0
2
0
2
0
0
2
0
3
0
3
0
1
3
0
0
1
0
0
3
0
0
3
0
2
0
0
0
0
0
0
0
0
 0
0
0
0
3
0
0
0
0
0
0
0
0
0
2
0
0
0
0
0
0
0
0
0
0
2
2
0
1
0
0
0
0
1
0
0
0
2
0
0
0
0
3
0
0
0
3
0
0
0
3
3
0
0
3
0
0
0
0
 3
3
3
1
3
3
3
2
2
1
3
3
3
1
3
1
2
1
0
2
3
2
2
2
3
1
3
3
3
3
2
2
3
2
3
2
3
2
3
1
2
3
2
3
3
1
3
2
3
 0
0
 2
0
2
 1
0
1
3
1
3
0
1
2
0
3
0
0
0
3
0
0
3
0
2
3
0
0
0
0
2
 0
0
0
0
0
0
0
0
0
0
0
                                                                0
0
                                                               0
                                                               0
 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
 0
0
0
0
 3
2
0
2
2
1
2
3
2
3
2
2
1
3
0
2
2
1
3
0
0
3
3
2
2
3
3
3
 3
3
3
1
0
3
0
2
1
3
3
3
1
2
3
3
1
3
3
1
3
3
3
2
2
1
0
0
0

/*
 * Package: StandardCodeLibrary.Core
 * */
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <utility>
#include <vector>
#include <list>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <numeric>
#include <bitset>
#include <complex>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <climits>
#if __GNUC__>=4 and __GNUC_MINOR__>=6
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#endif
#ifdef  __GXX_EXPERIMENTAL_CXX0X__
#define typeof decltype
#endif
using namespace std;

#define lp for(;;)
#define repf(i,a,b) for (int i=(a);i<(b);++i)
#define rep(i,n) repf(i,0,n)
#define ft(i,a,b) for (int i=(a);i<=(b);++i)
#define fdt(i,a,b) for (int i=(a);i>=(b);--i)
#define feach(e,s) for (typeof((s).begin()) e=(s).begin();e!=(s).end();++e)
#define fsubset(subset,set) for (int subset=(set)&((set)-1);subset;subset=(subset-1)&(set))
#define forin(i,charset) for (cstr i=(charset);*i;i++)
#define whl while
#define rtn return
#define fl(x,y) memset((x),char(y),sizeof(x))
#define clr(x) fl(x,char(0))
#define cpy(x,y) memcpy(x,y,sizeof(x))
#define pb push_back
#define mp make_pair
#define ins insert
#define ers erase
#define lb lower_bound
#define ub upper_bound
#define rnk order_of_key
#define sel find_by_order
#define x first
#define y second
#define sz(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
#define srt(x) sort(all(x))
#define uniq(x) srt(x),(x).erase(unique(all(x)),(x).end())
#define rev(x) reverse(all(x))
#define vec vector
#define pr pair
#define que queue
#define prq priority_queue
#define itr iterator
#define sf scanf
#define pf printf
#define pdb(prcs,x) (cout<<setprecision(prcs)<<fixed<<(sgn(x)?(x):0))
#ifdef DEBUG
#define prt(x) cerr<<#x"="<<(x)<<endl
#define asrtWA(s) do if(!(s))do{cerr<<"assert("#s")"<<endl;}whl(0);whl(0)
#define asrtTLE(s) do if(!(s))do{cerr<<"assert("#s")"<<endl;}whl(0);whl(0)
#define asrtMLE(s) do if(!(s))do{cerr<<"assert("#s")"<<endl;}whl(0);whl(0)
#define asrtOLE(s) do if(!(s))do{cerr<<"assert("#s")"<<endl;}whl(0);whl(0)
#define asrtRE(s) do if(!(s))do{cerr<<"assert("#s")"<<endl;}whl(0);whl(0)
#define runtime() cerr<<"Used: "<<db(clock())/CLOCKS_PER_SEC<<"s"<<endl
#define input(in) do{}whl(0)
#define output(out) do{}whl(0)
#else
#define endl (char('\n'))
#define prt(x) (cerr)
#define asrtWA(s) do if(!(s))exit(0);whl(0)
#define asrtTLE(s) do if(!(s))whl(1);whl(0)
#define asrtMLE(s) do if(!(s))whl(new int);whl(0)
#define asrtOLE(s) do if(!(s))whl(1)puts("OLE");whl(0)
#define asrtRE(s) do if(!(s))*(int*)0=0;whl(0)
#define runtime() (cerr)
#define input(in) freopen(in,"r",stdin)
#define output(out) freopen(out,"w",stdout)
#endif

typedef long long int lli;
typedef double db;
typedef const char* cstr;
typedef string str;
typedef vec<int> vi;
typedef vec<vi> vvi;
typedef vec<bool> vb;
typedef vec<vb> vvb;
typedef vec<str> vs;
typedef pr<int,int> pii;
typedef pr<lli,lli> pll;
typedef pr<db,db> pdd;
typedef map<int,int> mii;
typedef map<str,int> msi;
typedef map<char,int> mci;
typedef set<int> si;
typedef set<str> ss;
typedef que<int> qi;
typedef vec<pii> vpii;
typedef vec<pdd> vpdd;
#if __GNUC__>=4 and __GNUC_MINOR__>=6
using __gnu_cxx::rope;
#endif
#if __GNUC__>=4 and __GNUC_MINOR__>=7
template<typename key,typename value>class ext_map:public __gnu_pbds::tree<key,value,less<key>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>{};
template<typename key>class ext_set:public __gnu_pbds::tree<key,__gnu_pbds::null_type,less<key>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>{};
#elif __GNUC__>=4 and __GNUC_MINOR__>=6
template<typename key,typename value>class ext_map:public __gnu_pbds::tree<key,value,less<key>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>{};
template<typename key>class ext_set:public __gnu_pbds::tree<key,__gnu_pbds::null_mapped_type,less<key>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>{};
#endif

int oo=(~0u)>>1;
lli ooll=(~0ull)>>1;
db inf=1e+10;
db eps=1e-10;
db gam=0.5772156649015328606;
db pi=acos(-1.0);
int dx[]={1,0,-1,0,1,-1,-1,1,0};
int dy[]={0,1,0,-1,1,1,-1,-1,0};
int MOD=1000000007;

template<typename type>inline bool cmax(type& a,const type& b){rtn a<b?a=b,true:false;}
template<typename type>inline bool cmin(type& a,const type& b){rtn b<a?a=b,true:false;}
template<typename type>inline type sqr(const type& x){rtn x*x;}
inline int sgn(const db& x){rtn (x>+eps)-(x<-eps);}
inline int dbcmp(const db& a,const db& b){rtn sgn(a-b);}
template<typename istream,typename first_type,typename second_type>inline istream& operator>>(istream& cin,pr<first_type,second_type>& x){rtn cin>>x.x>>x.y;}
template<typename ostream,typename first_type,typename second_type>inline ostream& operator<<(ostream& cout,const pr<first_type,second_type>& x){rtn cout<<x.x<<" "<<x.y;}
template<typename istream,typename type>inline istream& operator>>(istream& cin,vec<type>& x){rep(i,sz(x))cin>>x[i];rtn cin;}
template<typename ostream,typename type>inline ostream& operator<<(ostream& cout,const vec<type>& x){rep(i,sz(x))cout<<x[i]<<(i+1==sz(x)?"":" ");rtn cout;}
template<typename type>inline pr<type,type> operator-(const pr<type,type>& x){rtn mp(-x.x,-x.y);}
template<typename type>inline pr<type,type> operator+(const pr<type,type>& a,const pr<type,type>& b){rtn mp(a.x+b.x,a.y+b.y);}
template<typename type>inline pr<type,type> operator-(const pr<type,type>& a,const pr<type,type>& b){rtn mp(a.x-b.x,a.y-b.y);}
template<typename type>inline pr<type,type> operator*(const pr<type,type>& a,const type& b){rtn mp(a.x*b,a.y*b);}
template<typename type>inline pr<type,type> operator/(const pr<type,type>& a,const type& b){rtn mp(a.x/b,a.y/b);}
template<typename type>inline pr<type,type>& operator-=(pr<type,type>& a,const pr<type,type>& b){rtn a=a-b;}
template<typename type>inline pr<type,type>& operator+=(pr<type,type>& a,const pr<type,type>& b){rtn a=a+b;}
template<typename type>inline pr<type,type>& operator*=(pr<type,type>& a,const type& b){rtn a=a*b;}
template<typename type>inline pr<type,type>& operator/=(pr<type,type>& a,const type& b){rtn a=a/b;}
template<typename type>inline type cross(const pr<type,type>& a,const pr<type,type>& b){rtn a.x*b.y-a.y*b.x;}
template<typename type>inline type dot(const pr<type,type>& a,const pr<type,type>& b){rtn a.x*b.x+a.y*b.y;}
template<typename type>inline type gcd(type a,type b){if(b)whl((a%=b)&&(b%=a));rtn a+b;}
template<typename type>inline type lcm(type a,type b){rtn a*b/gcd(a,b);}
template<typename type>inline void bit_inc(vec<type>& st,int x,type inc){whl(x<sz(st))st[x]+=inc,x|=x+1;}
template<typename type>inline type bit_sum(const vec<type>& st,int x){type s=0;whl(x>=0)s+=st[x],x=(x&(x+1))-1;rtn s;}
template<typename type>inline type bit_kth(const vec<type>& st,int k){int x=0,y=0,z=0;whl((1<<(++y))<=sz(st));fdt(i,y-1,0){if((x+=1<<i)>sz(st)||z+st[x-1]>k)x-=1<<i;else z+=st[x-1];}rtn x;}
inline void make_set(vi& st){rep(i,sz(st))st[i]=i;}
inline int find_set(vi& st,int x){int y=x,z;whl(y!=st[y])y=st[y];whl(x!=st[x])z=st[x],st[x]=y,x=z;rtn y;}
inline bool union_set(vi& st,int a,int b){a=find_set(st,a),b=find_set(st,b);rtn a!=b?st[a]=b,true:false;}
template<typename type>inline void merge(type& a,type& b){if(sz(a)<sz(b))swap(a,b);whl(sz(b))a.ins(*b.begin()),b.ers(b.begin());}

struct Initializer{Initializer(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}~Initializer(){runtime();}}initializer;

int md[201][201];
#define m(x,y) md[x+100][y+100]

int main()
{
	int n;
	cin>>n;
	m(0,0)=n;
	bool still=false;
	whl(!still)
	{
		still=true;
		ft(x,-100,100)
		ft(y,-100,100)
		{
			int get=m(x,y)/4;
			if (get)
			{
				rep(d,4)
					m(x+dx[d],y+dy[d])+=get;
				m(x,y)-=get*4;
				still=false;
			}
		}
	}
	int t;
	cin>>t;
	rep(i,t)
	{
		int x,y;
		if (max(abs(x),abs(y))<=100) cout<<m(x,y)<<endl;
		else cout<<0<<endl;
	}
}
