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 atcoder;

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//#include <boost/multiprecision/cpp_int.hpp>
using namespace std;


using dou =long double;
string yes="yes";
string Yes="Yes";
string YES="YES";
string no="no";
string No="No";
string NO="NO";

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007ll;
//const ll mod = 10000000000ll;
//const ll mod = 10000;

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
#define rep(i, n)         for(ll i = 0; i < (ll)(n); i++)
#define brep(n)           for(int bit=0;bit<(1<<n);bit++)
#define bbrep(n)           for(int bbit=0;bbit<(1<<n);bbit++)
#define erep(i,container) for (auto &i : container)
#define itrep(i,container) for (auto i : container)
#define irep(i, n)        for(ll i = n-1; i >= (ll)0ll; i--)
#define rrep(i,m,n) for(ll i = m; i < (ll)(n); i++)
#define reprep(i,j,h,w) rep(i,h)rep(j,w)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define VEC(type,name,n) std::vector<type> name(n);rep(i,n)std::cin >> name[i];
#define pb push_back
#define pf push_front
#define query int qq;std::cin >> qq;rep(qqq,qq)
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define itn int
#define mp make_pair
//#define sum(a) accumulate(all(a),0ll)
#define keta fixed<<setprecision
#define vout(a) erep(qxqxqx,a)std::cout << qxqxqx << ' ';std::cout  << std::endl;
#define vvector(name,typ,m,n,a)vector<vector<typ> > name(m,vector<typ> (n,a))
//#define vvector(name,typ,m,n)vector<vector<typ> > name(m,vector<typ> (n))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<t>(n,a)));
#define vvvvector(name,t,k,l,m,n,a) vector<vector<vector<vector<t> > > > name(k,vector<vector<vector<t> > >(l, vector<vector<t> >(m, vector<t>(n,a)) ));
#define case std::cout <<"Case #" <<qqq+1<<":"
#define RES(a,i,j) a.resize(i);rep(ii,i)a[ii].resize(j);
#define RESRES(a,i,j,k) a.resize(i);rep(ii,i)a[ii].resize(j);reprep(ii,jj,i,j){dp[ii][jj].resize(k)};
#define res resize
#define as assign
#define ffor for(;;)
#define ppri(a,b) std::cout << a<<" "<<b << std::endl
#define pppri(a,b,c) std::cout << a<<" "<<b <<" "<< c<<std::endl
#define ppppri(a,b,c,d) std::cout << a<<" "<<b <<" "<< c<<' '<<d<<std::endl
#define aall(x,n) (x).begin(),(x).begin()+(n)
#define SUM(a) accumulate(a,0ll) 
#define stirng string
#define gin(a,b) int a,b;std::cin >> a>>b;a--;b--;
#define popcount __builtin_popcount
#define permu(a) next_permutation(all(a))
//#define grid_input(a,type) int h,w;std::cin >> h>>w;vvector(a,type,h,w,0);reprep(i,j,h,w)std::cin >> a[i][j];

//typedef long long T;
ll ceil(ll a,ll b){
    return ((a+b-1)/b);
}
const int INF = 2000000000;
//const ll INF64 =3223372036854775807ll;
//const ll INF64 = 9223372036854775807ll;
const ll INF64 = 9223372036854775ll;
const ll MOD = 1000000007ll;
//const ll MOD = 1000003ll;
const ll OD = 1000000000000007ll;
const dou pi=3.141592653589793;
long long modpow(long long a, long long n,ll MOD) { //累乗の余剰
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}


//メモ
//ゲーム(Grundy数とか)の復習をする
//群論の勉強をする？
//ドツボにハマったら頑張って今までの思考をリセットする
//学会のスライドを作る(水曜日まで)
//周期性の実験をする
//リスニング力をどうにかする
//GT学会の会費を払う
/*
#include <atcoder/all>
using namespace atcoder;
*/
/*
#include <atcoder/all>
using namespace atcoder;
*/


int main(){
    int n,q;
    std::cin >> n>>q;
    rep(iii,q){
        int a,b;
        std::cin >> a>>b;
        if(n==1){
            std::cout << min(a,b) << std::endl;
            continue;
        }
        a--;b--;
        
        std::set<int> s;
        s.insert(a);
        while(a!=0){
            a=ceil(a,n)-1;
            s.insert(a);
        }
        ffor{
            if(s.find(b)!=s.end()){
                std::cout << b+1 << std::endl;
                break;
            }
            b=ceil(b,n)-1;
        }
    }
}