// Author : Naveen

// Program Start
// Libraries and Namespace Start
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
// Libraries and Namespace End

//----------------------------------------------------------------

// Important Shortcuts Start
// Custom Hash Function Start
struct custom_hash
{
    static uint64_t splitmix64(uint64_t x)
    {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
// Custom Hash Function End

// Declarations Start
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tll;
typedef stack<ll> stll;
typedef queue<ll> qll;
typedef vector<bool> vb;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef vector<pll> vpll;
typedef vector<tll> vtll;
typedef vector<ld> vld;
typedef set<ll> sll;
typedef unordered_set<ll, custom_hash> usll;
typedef multiset<ll> msll;
typedef unordered_multiset<ll, custom_hash> umsll;
typedef map<ll, ll> mll;
typedef unordered_map<ll, ll, custom_hash> umll;
typedef multimap<ll, ll> mmll;
typedef unordered_multimap<ll, ll, custom_hash> ummll;
typedef priority_queue<ll> maxheap;
typedef priority_queue<pll, vector<pll>, less<pll>> maxheappll;
typedef priority_queue<ll, vector<ll>, greater<ll>> minheap;
typedef priority_queue<pll, vector<pll>, greater<pll>> minheappll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbdssll;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> pbdmsll;
typedef tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update> pbdsmll;
typedef tree<pll, null_type, less_equal<pll>, rb_tree_tag, tree_order_statistics_node_update> pbdsmmll;
// Declarations End

// Constants Start
const ull mod1 = 1000000007LL;
const ull mod2 = 998244353LL;
const ull maxif = 1000000LL;
const ull inf = 9223372036854775807LL;
const ll ninf = -9223372036854775807LL - 1;
// Constants End

// Lib Functions Start
#define spc ' '
#define newl '\n'
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define yes cout << "yes\n"
#define no cout << "no\n"
#define Yes cout << "Yes\n"
#define No cout << "No\n"
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define all(v) v.begin(), v.end()
#define frin(i, s, e) for (ll i = s; i < e; i++)
#define frdec(i, e, s) for (ll i = e; i > s; i--)
#define frinv(i, s, e, v) for (ll i = s; i < e; i += v)
#define frdecv(i, e, s, v) for (ll i = e; i > s; i -= v)
// Lib Functions End

// Input and Output Functions Start
template <class T>
istream &operator>>(istream &is, vector<T> &a)
{
    for (T &x : a)
        is >> x;
    return is;
}

inline void yn(bool con)
{
    cout << (con ? "yes" : "no") << '\n';
}
inline void Yn(bool con)
{
    cout << (con ? "Yes" : "No") << '\n';
}
inline void YN(bool con)
{
    cout << (con ? "YES" : "NO") << '\n';
}

template <class T>
inline void print(const T &val)
{
    cout << val << ' ';
}
template <class T>
void print(const vector<T> &vec)
{
    for (T i : vec)
        cout << i << ' ';
}

template <class T>
inline void println(const T &val)
{
    cout << val << '\n';
}
template <class T>
void println(const vector<T> &vec)
{
    for (T i : vec)
        cout << i << ' ';
    cout << '\n';
}

template <class T, class V>
ostream &operator<<(ostream &os, const pair<T, V> &p)
{
    os << "(" << p.F << ", " << p.S << ")";
    return os;
}
template <size_t Index, typename... Types>
typename enable_if<Index == sizeof...(Types)>::type
printuplehelper(ostream &os, const tuple<Types...> &) {}
template <size_t Index, typename... Types>
    typename enable_if < Index<sizeof...(Types)>::type
                         printuplehelper(ostream &os, const tuple<Types...> &t)
{
    os << get<Index>(t);
    if (Index + 1 < sizeof...(Types))
        os << ", ";
    printuplehelper<Index + 1>(os, t);
}
template <typename... Types>
ostream &operator<<(ostream &os, const tuple<Types...> &t)
{
    os << "(";
    printuplehelper<0>(os, t);
    os << ")";
    return os;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec)
{
    size_t c = 0;
    const size_t n = vec.size();
    os << "[";
    for (T i : vec)
        os << i << (++c < n ? ", " : "");
    os << "]";
    return os;
}
template <class T>
ostream &operator<<(ostream &os, const set<T> &seti)
{
    size_t c = 0;
    const size_t n = seti.size();
    os << "{";
    for (T i : seti)
        os << i << (++c < n ? ", " : "");
    os << "}";
    return os;
}
template <class T>
ostream &operator<<(ostream &os, const multiset<T> &seti)
{
    size_t c = 0;
    const size_t n = seti.size();
    os << "{";
    for (T i : seti)
        os << i << (++c < n ? ", " : "");
    os << "}";
    return os;
}
template <class T, class V>
ostream &operator<<(ostream &os, const map<T, V> dict)
{
    size_t c = 0;
    const size_t n = dict.size();
    os << "{";
    for (auto it : dict)
        os << it.first << ": " << it.second << (++c < n ? ", " : "");
    os << "}";
    return os;
}
template <class T, class V>
ostream &operator<<(ostream &os, const unordered_map<T, V> dict)
{
    size_t c = 0;
    const size_t n = dict.size();
    os << "{";
    for (auto it : dict)
        os << it.first << ": " << it.second << (++c < n ? ", " : "");
    os << "}";
    return os;
}
// Input and Output Functions End
// Important Shortcuts End

//----------------------------------------------------------------

// Basic Functions Start
// String Operator Overload Start
template <class T>
string operator*(const string &str, const T &n)
{
    string res;
    res.reserve(str.size() * n);
    for (T i = 0; i < n; ++i)
        res += str;
    return res;
}
// String Operator Overload End

// Min Function Start
template <class T>
inline T min(const vector<T> &vec)
{
    return *min_element(vec.begin(), vec.end());
}
// Min Function End

// Max Function Start
template <class T>
inline T max(const vector<T> &vec)
{
    return *max_element(vec.begin(), vec.end());
}
// Max Function End

// Sum Function Start
template <class T>
inline T sum(const T &val)
{
    return val;
}
template <class T, class... Args>
T sum(const T &val, Args &&...args)
{
    return val + sum(forward<Args>(args)...);
}
template <class T>
inline T sum(const vector<T> &vec)
{
    return accumulate(vec.begin(), vec.end(), T(0));
}
// Sum Function End

// Binary Start
template <class T>
string bin(const T &dn)
{
    string binstr = bitset<64>(dn).to_string();
    ull firstone = binstr.find('1');
    if (firstone != string::npos)
    {
        binstr = binstr.substr(firstone);
        return binstr;
    }
    return "0";
}

ull int2(const string &binstr)
{
    bitset<64> bits(binstr);
    ull dn = static_cast<ull>(bits.to_ulong());
    return dn;
}
// Binary End

// Squareroot Start
inline ull sqrtint(ll n)
{
    if (n < 0)
        throw runtime_error("The number can't be negative.");
    return static_cast<ull>(sqrt(n));
}

ull sqrtintu(ll n)
{
    if (n < 0)
        throw runtime_error("The number can't be negative.");
    ull k = sqrt(n);
    return k * k == n ? k : k + 1;
}
// Squareroot End

// Map Computation Start
template <class T>
void mapcom(map<T, ll> &ma, const vector<T> &vec)
{
    for (T i : vec)
        ma[i]++;
}
// Map Computation End

// Binary Exponentiation Start
ull power(ull b, ull p)
{
    ull res = 1;
    while (p > 0)
    {
        if (p & 1)
            res = res * b;
        b = b * b;
        p >>= 1;
    }
    return res;
}
ull power(ull b, ull p, const ull mod)
{
    ull res = 1;
    b %= mod;
    while (p > 0)
    {
        if (p & 1)
            res = res * b % mod;
        b = b * b % mod;
        p >>= 1;
    }
    return res;
}
// Binary Exponentiation End

// Prime Number Start
bool isprime(ll n, bool p)
{
    if (n <= 0)
        throw runtime_error("The given number can't be negative.");
    if (n == 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (ll i = 5; i < (int)sqrt(n) + 1; i += 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}
bool isprime(ll n)
{
    if (n <= 0)
        throw runtime_error("The given number can't be negative.");
    if (n == 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    ull d = n - 1;
    while (d % 2 == 0)
        d /= 2;
    auto miller = [&](ull a)
    {
        if (a % n == 0)
            return true;
        ull x = power(a, d, n);
        if (x == 1 || x == n - 1)
            return true;
        ull c = d;
        while (c < n - 1)
        {
            x = x * x % n;
            if (x == n - 1)
                return true;
            c <<= 1;
        }
        return false;
    };
    vector<ull> bases64 = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    vector<ull> bases32 = {2, 7, 61};
    vector<ull> &bases = n <= 4294967296ull ? bases32 : bases64;
    for (ull base : bases)
        if (!miller(base))
            return false;
    return true;
}

void primes(vector<ll> &prime, const ull size = maxif)
{
    ull i, j;
    vector<bool> primeis(size + 1, true);
    primeis[0] = false;
    primeis[1] = false;
    for (i = 2; i <= sqrtintu(size); ++i)
        if (primeis[i])
            for (j = i * i; j <= size; j += i)
                primeis[j] = false;
    for (i = 2; i <= size; ++i)
        if (primeis[i])
            prime.pb(i);
}
// Prime Number End

// KMP Algorithm Start
ll substrisin(const string &text, const string &pattern)
{
    const size_t m = pattern.size();
    const size_t n = text.size();
    vll lps(m, 0);
    ll len = 0, i = 1, j;
    while (i < m)
    {
        if (pattern[i] == pattern[len])
        {
            len++;
            lps[i++] = len;
        }
        else
        {
            if (len != 0)
                len = lps[len - 1];
            else
                lps[i++] = 0;
        }
    }
    i = 0, j = 0;
    while (i < n)
    {
        if (pattern[j] == text[i])
        {
            ++i;
            ++j;
        }
        if (j == m)
            return i - j;
        else if (i < n && pattern[j] != text[i])
        {
            if (j != 0)
                j = lps[j - 1];
            else
                ++i;
        }
    }
    return -1;
}
// KMP Algorithm End
// Basic Functions End

//-----------------------------------------------------------------

// Modular Arithmetic Start
// Modinv Function Start
ll modinv(ll n, const ll mod, ll p)
{
    if (n < 0)
        throw runtime_error("The number can't be negative.");
    ll t1 = 0, t2 = 1, r1 = mod, r2 = n, q, temp;
    while (r2)
    {
        q = r1 / r2;
        temp = t1;
        t1 = t2;
        t2 = temp - q * t1;
        temp = r1;
        r1 = r2;
        r2 = temp - q * r1;
    }
    if (r1 > 1)
        throw runtime_error("Modular inverse does not exis.");
    return (t1 % mod + mod) % mod;
}
inline ll modinv(ll n, const ll mod = mod1)
{
    if (n < 0)
        throw runtime_error("The number can't be negative.");
    return power(n, mod - 2, mod);
}
// Modinv Function End

// Permutations and Combinations Start
inline ull fact(ll n)
{
    if (n < 0)
        throw runtime_error("The number can't be negative.");
    ull facto = 1;
    for (ull i = 1; i <= n; ++i)
        facto *= i;
    return facto;
}
inline ull fact(ll n, const ull mod)
{
    if (n < 0)
        throw runtime_error("The number can't be negative.");
    ull ans = 1;
    for (ull i = 1; i <= n; ++i)
        ans = ans * i % mod;
    return ans;
}

inline void factcom(vector<ll> &v)
{
    v[0] = 1;
    const size_t n = v.size();
    for (size_t i = 1; i < n; ++i)
        v[i] = i * v[i - 1];
}
inline void factcom(vector<ll> &v, const ll mod)
{
    v[0] = 1;
    const size_t n = v.size();
    for (size_t i = 1; i < n; ++i)
        v[i] = i * v[i - 1] % mod;
}

inline ull perm(ll n, ll r)
{
    if (n < 0 || r < 0)
        throw runtime_error("The numbers can't be negative.");
    ull ans = 1;
    for (ull i = n - r + 1; i <= n; ++i)
        ans *= i;
    return ans;
}
inline ull perm(ll n, ll r, const ull mod)
{
    if (n < 0 || r < 0)
        throw runtime_error("The numbers can't be negative.");
    ull ans = 1;
    for (ull i = n - r + 1; i <= n; ++i)
        ans = ans * i % mod;
    return ans;
}

ull comb(ll n, ll r)
{
    if (n < 0 || r < 0)
        throw runtime_error("The numbers can't be negative.");
    ull num = 1, den = 1;
    if (r > n / 2)
        r = n - r;
    n++;
    for (ull i = 1; i <= r; ++i)
    {
        num *= n - i;
        den *= i;
    }
    return num / den;
}
ull comb(ll n, ll r, const ull mod, bool p = 0)
{
    if (n < 0 || r < 0)
        throw runtime_error("The numbers can't be negative.");
    ull num = 1, den = 1;
    if (r > n / 2)
        r = n - r;
    n++;
    for (ull i = 1; i <= r; ++i)
    {
        num = num * (n - i) % mod;
        den = den * i % mod;
    }
    return num * ((!p) ? modinv(den, mod) : modinv(den, mod, 1)) % mod;
}

ull fastfib(ll n)
{
    if (n < 0)
        throw runtime_error("The numbers can't be negative.");
    ull a0 = 0, a1 = 1, f2, f21, t;
    for (ll i = 61; i >= 0; i--)
    {
        f2 = (a0 * (2 * a1 - a0));
        f21 = (a0 * a0 + a1 * a1);
        if (n & (1LL << i))
        {
            a0 = f21;
            a1 = f2 + f21;
        }
        else
        {
            a0 = f2;
            a1 = f21;
        }
    }
    return a0;
}
ull fastfib(ll n, const ull mod)
{
    if (n < 0)
        throw runtime_error("The numbers can't be negative.");
    ull a0 = 0, a1 = 1, f2, f21, t;
    for (ll i = 61; i >= 0; i--)
    {
        f2 = (a0 * (2 * a1 - a0)) %mod;
        f21 = (a0 * a0 + a1 * a1)%mod;
        if (n & (1LL << i))
        {
            a0 = f21;
            a1 = (f2 + f21)%mod;
        }
        else
        {
            a0 = f2;
            a1 = f21;
        }
    }
    return a0 % mod;
}
// Permuatations and Combinations End
// Modular Arithmetic End

// Data Structures Start
// Disjoint Set Union Start
class DisjointSet
{
private:
    vll parent, depth, setsize, maxset, minset;
    ull numsets;

public:
    DisjointSet() {}

    DisjointSet(ll n, ll start = 1)
    {
        init(n, start);
    }

    void init(ll n, ll start = 1)
    {
        numsets = n;
        n += start;
        parent.assign(n, 0);
        maxset.assign(n, 0);
        minset.assign(n, 0);
        for (ll i = start; i < n; i++)
            parent[i] = maxset[i] = minset[i] = i;
        depth.assign(n, 0);
        setsize.assign(n, 1);
    }

    ll findset(ll n)
    {
        return parent[n] = (parent[n] == n ? n : findset(parent[n]));
    }
    ll findset(ll n, bool p)
    {
        stack<ll> st;
        ll v;
        while (n != parent[n])
        {
            st.push(n);
            n = parent[n];
        }
        while (!st.empty())
        {
            v = st.top();
            st.pop();
            parent[v] = n;
        }
        return n;
    }

    bool issameset(ll a, ll b)
    {
        return findset(a) == findset(b);
    }

    void unionset(ll a, ll b)
    {
        ll x = findset(a), y = findset(b);
        if (x == y)
            return;
        if (depth[x] > depth[y])
            swap(x, y);
        if (depth[x] == depth[y])
            depth[y]++;
        parent[x] = y;
        setsize[y] += setsize[x];
        minset[y] = min(minset[y], minset[x]);
        maxset[y] = max(maxset[y], maxset[x]);
        numsets--;
    }

    ll numofsets()
    {
        return numsets;
    }

    ll sizeofset(ll n)
    {
        return setsize[findset(n)];
    }

    ll maxofset(ll n)
    {
        return maxset[findset(n)];
    }

    ll minofset(ll n)
    {
        return minset[findset(n)];
    }
};
// Disjoin Set Union End

// Segment Tree Start
template <class T>
class SegmentTree
{
private:
    const function<T(T, T)> &func;
    vector<T> tree;
    const size_t size;
    size_t queryLeft, queryRight, updateIndex, updateNewValue;

    void buildTree(size_t treeIndex, size_t left, size_t right)
    {
        if (left == right)
        {
            tree[treeIndex] = data[left];
            return;
        }
        size_t mid = left + (right - left) / 2;
        buildTree(2 * treeIndex + 1, left, mid);
        buildTree(2 * treeIndex + 2, mid + 1, right);
        tree[treeIndex] = func(tree[2 * treeIndex + 1], tree[2 * treeIndex + 2]);
    }

    T query(size_t treeIndex, size_t left, size_t right)
    {
        if (queryLeft <= left && right <= queryRight)
            return tree[treeIndex];
        size_t mid = left + (right - left) / 2;
        if (queryRight <= mid)
            return query(2 * treeIndex + 1, left, mid);
        if (queryLeft > mid)
            return query(2 * treeIndex + 2, mid + 1, right);
        return func(query(2 * treeIndex + 1, left, mid), query(2 * treeIndex + 2, mid + 1, right));
    }

    void update(size_t treeIndex, size_t left, size_t right)
    {
        if (left == right)
        {
            tree[treeIndex] = updateNewValue;
            return;
        }
        size_t mid = left + (right - left) / 2;
        if (updateIndex <= mid)
            update(2 * treeIndex + 1, left, mid);
        else
            update(2 * treeIndex + 2, mid + 1, right);
        tree[treeIndex] = func(tree[2 * treeIndex + 1], tree[2 * treeIndex + 2]);
    }

public:
    vector<T> data;

    SegmentTree(const vector<T> &vec, const function<T(T, T)> &fun) : size(vec.size()), func(fun), data(vec.begin(), vec.end())
    {
        tree.assign(2 * size - 1, 0);
        buildTree(0, 0, size - 1);
    }

    T query(ll left, ll right)
    {
        if (left > right || left < 0 || right >= size)
            throw runtime_error("Given query range is invalid or out of range.");
        queryLeft = left;
        queryRight = right;
        return query(0, 0, size - 1);
    }

    void update(ll index, T newValue)
    {
        if (index < 0 || index >= size)
            throw runtime_error("Given update index is out of range.");
        data[index] = newValue;
        updateIndex = index;
        updateNewValue = newValue;
        update(0, 0, size - 1);
    }
};
// Segment Tree End

// Graphs Start
// Unweighted Graphs Start
class UnweightedGraph
{
private:
    ll count;

    void dfspr(ll src)
    {
        visited[src] = true;
        pre[src] = count;
        count++;
        for (auto it : alist[src])
        {
            if (!visited[it])
            {
                parent[it] = src;
                dfspr(it);
            }
        }
        post[src] = count;
        count++;
    }

public:
    vector<vll> alist;
    vb visited;
    vll level, component, topoorder, pathlen, parent, pre, post;
    ll start, end, numofcomp;

    UnweightedGraph(const vector<vll> &alis, ll star = 1)
    {
        alist = alis;
        start = star;
        end = alis.size() + start;
    }

    void dfs(ll src, bool iter = true)
    {
        visited.assign(end, false);
        parent.assign(end, -1);
        pre.assign(end, -1);
        post.assign(end, -1);
        if (iter)
        {
            ll cou = 0;
            stack<ll> st;
            ll u;
            bool flag;
            st.push(src);
            while (!st.empty())
            {
                u = st.top();
                if (!visited[u])
                {
                    visited[u] = true;
                    pre[u] = cou;
                    cou++;
                }
                flag = true;
                for (ll v : alist[u])
                {
                    if (!visited[v])
                    {
                        parent[v] = u;
                        st.push(v);
                        flag = false;
                        break;
                    }
                }
                if (flag)
                {
                    post[u] = cou;
                    cou++;
                    st.pop();
                }
            }
        }
        else
        {
            count = 0;
            dfspr(src);
        }
    }

    void bfs(ll src)
    {
        level.assign(end, -1);
        parent.assign(end, -1);
        queue<ll> que;
        que.push(src);
        level[src] = 0;
        ll v;
        while (!que.empty())
        {
            v = que.front();
            que.pop();
            for (auto it : alist[v])
            {
                if (level[it] == -1)
                {
                    level[it] = level[v] + 1;
                    parent[it] = v;
                    que.push(it);
                }
            }
        }
    }

    void components()
    {
        component.assign(end, -1);
        ll seen = start, src, i;
        numofcomp = 0;
        while (seen < end)
        {
            src = -1;
            for (i = start; i < end; i++)
            {
                if (component[i] == -1)
                {
                    src = i;
                    break;
                }
            }
            bfs(src);
            for (auto it : level)
            {
                if (level[it] != -1)
                {
                    component[it] = numofcomp;
                    seen++;
                }
            }
            numofcomp++;
        }
    }

    void topologicalorder()
    {
        vll indegree(end, 0);
        pathlen.assign(end, 0);
        ll i;
        for (i = start; i < end; i++)
        {
            for (auto it : alist[i])
            {
                indegree[it]++;
            }
        }
        queue<ll> que;
        for (i = start; i < end; i++)
            if (indegree[i] == 0)
                que.push(i);
        ll v;
        while (!que.empty())
        {
            v = que.front();
            que.pop();
            topoorder.pb(v);
            indegree[v] = -1;
            for (auto it : alist[v])
            {
                indegree[it]--;
                pathlen[it] = max(pathlen[it], pathlen[v] + 1);
                if (indegree[it] == 0)
                    que.push(it);
            }
        }
    }
};
// Unweighted Graphs End

// Weighted Graphs Start
class WeightedGraph
{
public:
    vector<vpll> wlist;
    vector<vll> distancefw;
    DisjointSet component;
    vpll edge;
    vll distance;
    ll start, end;

    WeightedGraph(const vector<vpll> &wlis, ll star = 1)
    {
        wlist = wlis;
        start = star;
        end = wlis.size() + star;
    }

    void dijkstra(ll src)
    {
        vb visited(end, false);
        distance.assign(end, inf);
        distance[src] = 0;
        minheappll heap;
        heap.push({0, src});
        ll nextv;
        while (!heap.empty())
        {
            nextv = heap.top().S;
            heap.pop();
            if (visited[nextv])
                continue;
            visited[nextv] = true;
            for (auto it : wlist[nextv])
            {
                if (!visited[it.F] && distance[nextv] + it.S < distance[it.F])
                {
                    distance[it.F] = distance[nextv] + it.S;
                    heap.push({distance[it.F], it.F});
                }
            }
        }
    }

    void bellmanford(ll src)
    {
        distance.assign(end, inf);
        distance[src] = 0;
        ll i, u;
        for (i = start; i < end - 1; i++)
            for (u = start; u < end; u++)
                for (auto it : wlist[u])
                    distance[it.F] = min(distance[it.F], distance[u] + it.S);
        bool flag = false;
        for (u = start; u < end; u++)
            for (auto it : wlist[u])
                if (distance[u] + it.S < distance[it.F])
                    throw runtime_error("The graph has negative cycles.");
    }

    void floydwarshall()
    {
        distancefw.assign(end, vll(end, inf));
        ll i, j, k;
        for (i = start; i < end; i++)
            for (auto it : wlist[i])
                distancefw[i][it.F] = it.S;
        for (i = start; i < end; i++)
            for (j = start; j < end; j++)
                for (k = start; k < end; k++)
                    distancefw[j][k] = min(distancefw[j][k], distancefw[j][i] + distancefw[i][k]);
    }

    void prim()
    {
        vb visited(end, false);
        distance.assign(end, inf);
        distance[start] = 0;
        minheappll heap;
        heap.push({0, start});
        ll nextv;
        while (!heap.empty())
        {
            nextv = heap.top().S;
            if (visited[nextv])
                continue;
            visited[nextv] = true;
            for (auto it : wlist[nextv])
            {
                if (!visited[it.F] && it.S < distance[it.F])
                {
                    distance[it.F] = it.S;
                    heap.push({it.S, it.F});
                }
            }
        }
    }

    void kruskal()
    {
        component.init(end - start, start);
        set<tll> edges;
        ll u, v;
        for (u = start; u < end; u++)
            for (auto it : wlist[u])
                edges.insert({it.S, u, it.F});
        for (auto it : edges)
        {
            u = get<1>(it);
            v = get<2>(it);
            if (component.issameset(u, v))
                continue;
            edge.pb({u, v});
            component.unionset(u, v);
        }
    }
};
// Weighted Graphs End
// Graphs End
// Data Structures End

//----------------------------------------------------------------

// Solution Class Start
class Solution
{
public:
    void solve(ull index)
    {
        //----------------------------------------------------------------

        ll n, i, j, k;
        cin >> n;
        vll arr(n);
        cin >> arr;
        ll q;
        cin >> q;
        SegmentTree<ll> s1(arr, [](ll a, ll b){
            return a>b?a:b;
        });
        SegmentTree<ll> s2(arr, [](ll a, ll b){
            ll t;
            while(b)
            {
                t = b;
                b = a%b;
                a = t;
            }
            return a;
        });
        ll l, r, maxi=0, ansl=0, ansr=0, val=0;
        while (q--)
        {
            cin >> l >> r;
            val = s1.query(l-1, r-1)/s2.query(l-1, r-1);
            if(val>maxi)
            {
                maxi = val;
                ansl = l;
                ansr = r;
            }
        }
        cout<<ansl<<spc<<ansr<<spc<<maxi<<newl;

        // cout << "Case #" << index << ": " << ans << newl;

        //----------------------------------------------------------------
    }

    bool testCases = true;
};
// Solution Class End

// Main Function Start
int32_t main()
{
    Solution sol;
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ull test = 1;
    if (sol.testCases)
        cin >> test;
    for (ull i = 1; i <= test; i++)
        sol.solve(i);
    return 0;
}
// Main Function End
// Program End
//----------------------------------------------------------------