Problem: You are given an integer N. Consider an infinite N-ary tree as shown below:

<image>

Figure: an infinite N-ary tree for the case N = 3

As shown in the figure, each vertex is indexed with a unique positive integer, and for every positive integer there is a vertex indexed with it. The root of the tree has the index 1. For the remaining vertices, vertices in the upper row have smaller indices than those in the lower row. Among the vertices in the same row, a vertex that is more to the left has a smaller index.

Regarding this tree, process Q queries. The i-th query is as follows:

* Find the index of the lowest common ancestor (see Notes) of Vertex v_i and w_i.

Constraints

* 1 ≤ N ≤ 10^9
* 1 ≤ Q ≤ 10^5
* 1 ≤ v_i < w_i ≤ 10^9

Input

Input is given from Standard Input in the following format:


N Q
v_1 w_1
:
v_Q w_Q


Output

Print Q lines. The i-th line (1 ≤ i ≤ Q) must contain the index of the lowest common ancestor of Vertex v_i and w_i.

Examples

Input

3 3
5 7
8 11
3 9


Output

2
1
3


Input

100000 2
1 2
3 4


Output

1
1

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
typedef long long   signed int LL;
typedef long long unsigned int LU;
#define incII(i, l, r) for(int i = (l)    ; i <= (r); ++i)
#define incID(i, l, r) for(int i = (l)    ; i <  (r); ++i)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); --i)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i)
#define inc(i, n)  incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec(i, n)  decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)
#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
template<typename T> bool setmin  (T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmax  (T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
LL mo(LL a, LL b) { assert(b > 0); a %= b; if(a < 0) { a += b; } return a; }
LL fl(LL a, LL b) { assert(b > 0); return (a > 0 ? a / b : (a - b + 1) / b); }
LL ce(LL a, LL b) { assert(b > 0); return (a < 0 ? a / b : (a + b - 1) / b); }
#define bit(b, i) (((b) >> (i)) & 1)
#define BC __builtin_popcountll
#define SC(T, v) static_cast<T>(v)
#define SI(v) SC(int, v.size())
#define SL(v) SC( LL, v.size())
#define RF(e, v) for(auto & e: v)
#define ei else if
#define UR assert(false)

// ---- ----

int n, q;

void p(int & a) { a = (a - 1) / n; }

int d(int a) {
	int c = 0;
	while(a != 0) { p(a); c++; }
	return c;
}

int main() {
	cin >> n >> q;
	inc(qq, q) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		
		if(n == 1) {
			cout << min(a, b) + 1 << "\n";
		} else {
			int aa = d(a);
			int bb = d(b);
			int c = abs(aa - bb);
			if(aa > bb) { inc(i, c) { p(a); } }
			if(bb > aa) { inc(i, c) { p(b); } }
			while(a != b) { p(a); p(b); }
			cout << a + 1 << "\n";
		}
	}
	
	return 0;
}