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

#include <Bits/stdc++.h>
using namespace std ;
const int range = 1010 ;
int ans[range][range] ;
void dfs ( int x , int y ) {
	if ( ans[x][y] < 3 ) return ;
	else {
		ans[x - 1][y] += ans[x][y] / 4 ;
		ans[x][y - 1] += ans[x][y] / 4 ;
		ans[x + 1][y] += ans[x][y] / 4 ;
		ans[x][y - 1] += ans[x][y] / 4 ;
	}
}
int main(int argc, char** argv) {
	int n , t , x , y ;
	cin >> n >> t ;
	ans[range / 2][range / 2] = n ;
	dfs ( range / 2 , range / 2 ) ;
	for ( int i = 0 ; i < t ; i ++ ) {
		cin >> x >> y ;
		if ( x <= -range / 2 or x >= range / 2 or y <= -range / 2 or y >= range / 2 ) cout << 0 << endl ;
		else cout << ans[x + range / 2][y + range / 2] << endl ;
	}
	return 0;
}
