#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <functional>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string.h>
#include <type_traits>
#include <unordered_map>
#if __cplusplus < 201703L
namespace std {
template <typename _Tp>
  constexpr bool is_void_v = is_void<_Tp>::value;
template <typename _Tp>
  constexpr bool is_null_pointer_v = is_null_pointer<_Tp>::value;
template <typename _Tp>
  constexpr bool is_integral_v = is_integral<_Tp>::value;
template <typename _Tp>
  constexpr bool is_floating_point_v = is_floating_point<_Tp>::value;
template <typename _Tp>
  constexpr bool is_array_v = is_array<_Tp>::value;
template <typename _Tp>
  constexpr bool is_pointer_v = is_pointer<_Tp>::value;
template <typename _Tp>
  constexpr bool is_lvalue_reference_v =
    is_lvalue_reference<_Tp>::value;
template <typename _Tp>
  constexpr bool is_rvalue_reference_v =
    is_rvalue_reference<_Tp>::value;
template <typename _Tp>
  constexpr bool is_member_object_pointer_v =
    is_member_object_pointer<_Tp>::value;
template <typename _Tp>
  constexpr bool is_member_function_pointer_v =
    is_member_function_pointer<_Tp>::value;
template <typename _Tp>
  constexpr bool is_enum_v = is_enum<_Tp>::value;
template <typename _Tp>
  constexpr bool is_union_v = is_union<_Tp>::value;
template <typename _Tp>
  constexpr bool is_class_v = is_class<_Tp>::value;
template <typename _Tp>
  constexpr bool is_function_v = is_function<_Tp>::value;
template <typename _Tp>
  constexpr bool is_reference_v = is_reference<_Tp>::value;
template <typename _Tp>
  constexpr bool is_arithmetic_v = is_arithmetic<_Tp>::value;
template <typename _Tp>
  constexpr bool is_fundamental_v = is_fundamental<_Tp>::value;
template <typename _Tp>
  constexpr bool is_object_v = is_object<_Tp>::value;
template <typename _Tp>
  constexpr bool is_scalar_v = is_scalar<_Tp>::value;
template <typename _Tp>
  constexpr bool is_compound_v = is_compound<_Tp>::value;
template <typename _Tp>
  constexpr bool is_member_pointer_v = is_member_pointer<_Tp>::value;
template <typename _Tp>
  constexpr bool is_const_v = is_const<_Tp>::value;
template <typename _Tp>
  constexpr bool is_volatile_v = is_volatile<_Tp>::value;
template <typename _Tp>
  constexpr bool is_trivial_v = is_trivial<_Tp>::value;
template <typename _Tp>
  constexpr bool is_trivially_copyable_v =
    is_trivially_copyable<_Tp>::value;
template <typename _Tp>
  constexpr bool is_standard_layout_v = is_standard_layout<_Tp>::value;
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wdeprecated-declarations"
template <typename _Tp>
  [[deprecated("use is_standard_layout_v && is_trivial_v instead")]]
  constexpr bool is_pod_v = is_pod<_Tp>::value;
#pragma GCC diagnostic pop
template <typename _Tp>
  constexpr bool is_literal_type_v = is_literal_type<_Tp>::value;
template <typename _Tp>
  constexpr bool is_empty_v = is_empty<_Tp>::value;
template <typename _Tp>
  constexpr bool is_polymorphic_v = is_polymorphic<_Tp>::value;
template <typename _Tp>
  constexpr bool is_abstract_v = is_abstract<_Tp>::value;
template <typename _Tp>
  constexpr bool is_final_v = is_final<_Tp>::value;
template <typename _Tp>
  constexpr bool is_signed_v = is_signed<_Tp>::value;
template <typename _Tp>
  constexpr bool is_unsigned_v = is_unsigned<_Tp>::value;
template <typename _Tp, typename... _Args>
  constexpr bool is_constructible_v =
    is_constructible<_Tp, _Args...>::value;
template <typename _Tp>
  constexpr bool is_default_constructible_v =
    is_default_constructible<_Tp>::value;
template <typename _Tp>
  constexpr bool is_copy_constructible_v =
    is_copy_constructible<_Tp>::value;
template <typename _Tp>
  constexpr bool is_move_constructible_v =
    is_move_constructible<_Tp>::value;
template <typename _Tp, typename _Up>
  constexpr bool is_assignable_v = is_assignable<_Tp, _Up>::value;
template <typename _Tp>
  constexpr bool is_copy_assignable_v = is_copy_assignable<_Tp>::value;
template <typename _Tp>
  constexpr bool is_move_assignable_v = is_move_assignable<_Tp>::value;
template <typename _Tp>
  constexpr bool is_destructible_v = is_destructible<_Tp>::value;
template <typename _Tp, typename... _Args>
  constexpr bool is_trivially_constructible_v =
    is_trivially_constructible<_Tp, _Args...>::value;
template <typename _Tp>
  constexpr bool is_trivially_default_constructible_v =
    is_trivially_default_constructible<_Tp>::value;
template <typename _Tp>
  constexpr bool is_trivially_copy_constructible_v =
    is_trivially_copy_constructible<_Tp>::value;
template <typename _Tp>
  constexpr bool is_trivially_move_constructible_v =
    is_trivially_move_constructible<_Tp>::value;
template <typename _Tp, typename _Up>
  constexpr bool is_trivially_assignable_v =
    is_trivially_assignable<_Tp, _Up>::value;
template <typename _Tp>
  constexpr bool is_trivially_copy_assignable_v =
    is_trivially_copy_assignable<_Tp>::value;
template <typename _Tp>
  constexpr bool is_trivially_move_assignable_v =
    is_trivially_move_assignable<_Tp>::value;
template <typename _Tp>
  constexpr bool is_trivially_destructible_v =
    is_trivially_destructible<_Tp>::value;
template <typename _Tp, typename... _Args>
  constexpr bool is_nothrow_constructible_v =
    is_nothrow_constructible<_Tp, _Args...>::value;
template <typename _Tp>
  constexpr bool is_nothrow_default_constructible_v =
    is_nothrow_default_constructible<_Tp>::value;
template <typename _Tp>
  constexpr bool is_nothrow_copy_constructible_v =
    is_nothrow_copy_constructible<_Tp>::value;
template <typename _Tp>
  constexpr bool is_nothrow_move_constructible_v =
    is_nothrow_move_constructible<_Tp>::value;
template <typename _Tp, typename _Up>
  constexpr bool is_nothrow_assignable_v =
    is_nothrow_assignable<_Tp, _Up>::value;
template <typename _Tp>
  constexpr bool is_nothrow_copy_assignable_v =
    is_nothrow_copy_assignable<_Tp>::value;
template <typename _Tp>
  constexpr bool is_nothrow_move_assignable_v =
    is_nothrow_move_assignable<_Tp>::value;
template <typename _Tp>
  constexpr bool is_nothrow_destructible_v =
    is_nothrow_destructible<_Tp>::value;
template <typename _Tp>
  constexpr bool has_virtual_destructor_v =
    has_virtual_destructor<_Tp>::value;
template <typename _Tp>
  constexpr size_t alignment_of_v = alignment_of<_Tp>::value;
template <typename _Tp>
  constexpr size_t rank_v = rank<_Tp>::value;
template <typename _Tp, unsigned _Idx = 0>
  constexpr size_t extent_v = extent<_Tp, _Idx>::value;
#ifdef _GLIBCXX_BUILTIN_IS_SAME_AS
template <typename _Tp, typename _Up>
  constexpr bool is_same_v = _GLIBCXX_BUILTIN_IS_SAME_AS(_Tp, _Up);
#else
template <typename _Tp, typename _Up>
  constexpr bool is_same_v = std::is_same<_Tp, _Up>::value;
#endif
template <typename _Base, typename _Derived>
  constexpr bool is_base_of_v = is_base_of<_Base, _Derived>::value;
template <typename _From, typename _To>
  constexpr bool is_convertible_v = is_convertible<_From, _To>::value;
}
#endif
namespace OY {
#define cin OY::inputHelper<1024, 20>::getInstance()
#define getchar() ({char c=cin.getChar_Checked();cin.next();c;})
#define cout OY::outputHelper<1048576>::getInstance()
#define putchar cout.putChar
#define endl '\n'
#define putlog(...) OY::printLog(", ", __VA_ARGS__)
    template <uint64_t _BufferSize = 1024, uint64_t _BlockSize = 20>
    class inputHelper {
        FILE *m_filePtr;
        char m_buf[_BufferSize], *m_end, *m_cursor;
        bool m_ok;
        void flush() {
            uint64_t a = m_end - m_cursor;
            if (a >= _BlockSize) return;
            memmove(m_buf, m_cursor, a);
            uint64_t b = fread(m_buf + a, 1, _BufferSize - a, m_filePtr);
            m_cursor = m_buf;
            if (a + b < _BufferSize) {
                m_end = m_buf + a + b;
                *m_end = EOF;
            }
        }

    public:
        explicit inputHelper(const char *inputFileName) : m_ok(true) {
            if (!*inputFileName)
                m_filePtr = stdin;
            else
                m_filePtr = fopen(inputFileName, "rt");
            m_end = m_cursor = m_buf + _BufferSize;
        }
        ~inputHelper() { fclose(m_filePtr); }
        static inputHelper<_BufferSize, _BlockSize> &getInstance() {
#ifdef OY_LOCAL
            static inputHelper<_BufferSize, _BlockSize> s_obj("in.txt");
#else
            static inputHelper<_BufferSize, _BlockSize> s_obj("");
#endif
            return s_obj;
        }
        static constexpr bool isBlank(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\r'; }
        static constexpr bool isEndline(char c) { return c == '\n' || c == EOF; }
        const char &getChar_Checked() {
            if (m_cursor < m_end) return *m_cursor;
            uint64_t b = fread(m_buf, 1, _BufferSize, m_filePtr);
            m_cursor = m_buf;
            if (b < _BufferSize) {
                m_end = m_buf + b;
                *m_end = EOF;
            }
            return *m_cursor;
        }
        const char &getChar_Unchecked() const { return *m_cursor; }
        void next() { ++m_cursor; }
        void setState(bool _ok) { m_ok = _ok; }
        template <typename _Tp, std::enable_if_t<std::is_signed_v<_Tp> & std::is_integral_v<_Tp>> * = nullptr>
        inputHelper<_BufferSize, _BlockSize> &operator>>(_Tp &ret) {
            while (isBlank(getChar_Checked())) next();
            flush();
            if (getChar_Unchecked() == '-') {
                next();
                if (isdigit(getChar_Unchecked())) {
                    ret = -(getChar_Unchecked() - '0');
                    while (next(), isdigit(getChar_Unchecked())) ret = ret * 10 - (getChar_Unchecked() - '0');
                } else
                    m_ok = false;
            } else {
                if (isdigit(getChar_Unchecked())) {
                    ret = getChar_Unchecked() - '0';
                    while (next(), isdigit(getChar_Unchecked())) ret = ret * 10 + (getChar_Unchecked() - '0');
                } else
                    m_ok = false;
            }
            return *this;
        }
        template <typename _Tp, std::enable_if_t<std::is_unsigned_v<_Tp> & std::is_integral_v<_Tp>> * = nullptr>
        inputHelper<_BufferSize, _BlockSize> &operator>>(_Tp &ret) {
            while (isBlank(getChar_Checked())) next();
            flush();
            if (isdigit(getChar_Unchecked())) {
                ret = getChar_Unchecked() - '0';
                while (next(), isdigit(getChar_Unchecked())) ret = ret * 10 + (getChar_Unchecked() - '0');
            } else
                m_ok = false;
            return *this;
        }
        template <typename _Tp, std::enable_if_t<std::is_floating_point_v<_Tp>> * = nullptr>
        inputHelper<_BufferSize, _BlockSize> &operator>>(_Tp &ret) {
            bool neg = false, integer = false, decimal = false;
            while (isBlank(getChar_Checked())) next();
            flush();
            if (getChar_Unchecked() == '-') {
                neg = true;
                next();
            }
            if (!isdigit(getChar_Unchecked()) && getChar_Unchecked() != '.') {
                m_ok = false;
                return *this;
            }
            if (isdigit(getChar_Unchecked())) {
                integer = true;
                ret = getChar_Unchecked() - '0';
                while (next(), isdigit(getChar_Unchecked())) ret = ret * 10 + (getChar_Unchecked() - '0');
            }
            if (getChar_Unchecked() == '.') {
                next();
                if (isdigit(getChar_Unchecked())) {
                    if (!integer) ret = 0;
                    decimal = true;
                    _Tp unit = 0.1;
                    ret += unit * (getChar_Unchecked() - '0');
                    while (next(), isdigit(getChar_Unchecked())) {
                        unit *= 0.1;
                        ret += unit * (getChar_Unchecked() - '0');
                    }
                }
            }
            if (!integer && !decimal)
                m_ok = false;
            else if (neg)
                ret = -ret;
            return *this;
        }
        inputHelper<_BufferSize, _BlockSize> &operator>>(char &ret) {
            while (isBlank(getChar_Checked())) next();
            ret = getChar_Checked();
            next();
            return *this;
        }
        inputHelper<_BufferSize, _BlockSize> &operator>>(std::string &ret) {
            while (isBlank(getChar_Checked())) next();
            if (getChar_Checked() != EOF) {
                ret.clear();
                do {
                    ret += getChar_Checked();
                    next();
                } while (!isBlank(getChar_Checked()) && getChar_Unchecked() != EOF);
            } else
                m_ok = false;
            return *this;
        }
        explicit operator bool() { return m_ok; }
    };
    template <uint64_t _BufferSize = 1048576>
    class outputHelper {
        FILE *m_filePtr = nullptr;
        char m_buf[_BufferSize], *m_end, *m_cursor;
        char m_tempBuf[50], *m_tempBufCursor, *m_tempBufDot;
        uint64_t m_floatReserve, m_floatRatio;

    public:
        outputHelper(const char *outputFileName, int prec = 6) : m_end(m_buf + _BufferSize) {
            if (!*outputFileName)
                m_filePtr = stdout;
            else
                m_filePtr = fopen(outputFileName, "wt");
            m_cursor = m_buf;
            m_tempBufCursor = m_tempBuf;
            precision(prec);
        }
        static outputHelper<_BufferSize> &getInstance() {
#ifdef OY_LOCAL
            static outputHelper<_BufferSize> s_obj("out.txt");
#else
            static outputHelper<_BufferSize> s_obj("");
#endif
            return s_obj;
        }
        ~outputHelper() {
            flush();
            fclose(m_filePtr);
        }
        void precision(int prec) {
            m_floatReserve = prec;
            m_floatRatio = pow(10, prec);
            m_tempBufDot = m_tempBuf + prec;
        }
        outputHelper<_BufferSize> &flush() {
            fwrite(m_buf, 1, m_cursor - m_buf, m_filePtr);
            fflush(m_filePtr);
            m_cursor = m_buf;
            return *this;
        }
        void putChar(const char &c) {
            if (m_cursor == m_end) flush();
            *m_cursor++ = c;
        }
        void putS(const char *c) {
            while (*c) putChar(*c++);
        }
        template <typename _Tp, std::enable_if_t<std::is_signed_v<_Tp> & std::is_integral_v<_Tp>> * = nullptr>
        outputHelper<_BufferSize> &operator<<(const _Tp &ret) {
            _Tp _ret = _Tp(ret);
            if (_ret >= 0) {
                do {
                    *m_tempBufCursor++ = '0' + _ret % 10;
                    _ret /= 10;
                } while (_ret);
                do putChar(*--m_tempBufCursor);
                while (m_tempBufCursor > m_tempBuf);
            } else {
                putChar('-');
                do {
                    *m_tempBufCursor++ = '0' - _ret % 10;
                    _ret /= 10;
                } while (_ret);
                do putChar(*--m_tempBufCursor);
                while (m_tempBufCursor > m_tempBuf);
            }
            return *this;
        }
        template <typename _Tp, std::enable_if_t<std::is_unsigned_v<_Tp> & std::is_integral_v<_Tp>> * = nullptr>
        outputHelper<_BufferSize> &operator<<(const _Tp &ret) {
            _Tp _ret = _Tp(ret);
            do {
                *m_tempBufCursor++ = '0' + _ret % 10;
                _ret /= 10;
            } while (_ret);
            do putChar(*--m_tempBufCursor);
            while (m_tempBufCursor > m_tempBuf);
            return *this;
        }
        template <typename _Tp, std::enable_if_t<std::is_floating_point_v<_Tp>> * = nullptr>
        outputHelper<_BufferSize> &operator<<(const _Tp &ret) {
            if (ret < 0) {
                putChar('-');
                return *this << -ret;
            }
            _Tp _ret = ret * m_floatRatio;
            uint64_t integer = _ret;
            if (_ret - integer >= 0.4999999999) integer++;
            do {
                *m_tempBufCursor++ = '0' + integer % 10;
                integer /= 10;
            } while (integer);
            if (m_tempBufCursor > m_tempBufDot) {
                do putChar(*--m_tempBufCursor);
                while (m_tempBufCursor > m_tempBufDot);
                putChar('.');
            } else {
                putS("0.");
                for (int i = m_tempBufDot - m_tempBufCursor; i--;) putChar('0');
            }
            do putChar(*--m_tempBufCursor);
            while (m_tempBufCursor > m_tempBuf);
            return *this;
        }
        outputHelper<_BufferSize> &operator<<(const char &ret) {
            putChar(ret);
            return *this;
        }
        outputHelper<_BufferSize> &operator<<(const std::string &ret) {
            putS(ret.data());
            return *this;
        }
    };
    template <uint64_t _BufferSize, uint64_t _BlockSize>
    inputHelper<_BufferSize, _BlockSize> &getline(inputHelper<_BufferSize, _BlockSize> &ih, std::string &ret) {
        ret.clear();
        if (ih.getChar_Checked() == EOF)
            ih.setState(0);
        else {
            while (!inputHelper<_BufferSize, _BlockSize>::isEndline(ih.getChar_Checked())) {
                ret += ih.getChar_Unchecked();
                ih.next();
            }
            ih.next();
        }
        return ih;
    }
    template <typename D, typename T, typename... S>
    void printLog(D delim, const T &x, S... rest) {
        cout << x;
        if constexpr (sizeof...(rest) > 0) {
            cout << delim;
            printLog(delim, rest...);
        }
    }
}
using OY::getline;
using std::vector;
#define int long long
const int MAXN = 524291;
const long double pi = 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679821480865132823066470938446095505822317253594081284811174502841027019385211055596446229489549303819644288109756659334461284756482337867831652712019091456485669234603486104543266482133936072602491412737245870066063155881748815209209628292540917153643678925903600113305305488204665213841469519415116094330572703657595919530921861173819326117931051185480744623799627495673518857527248912279381830119491298336733624406566430860213949463952247371907021798609437027705392171762931767523846748184676694051320005681271452635608277857713427577896091736371787214684409012249534301465495853710507922796892589235420199561121290219608640344181598136297747713099605187072113499999983729780499510597317328160963185950244594553469083026425223082533446850352619311881710100031378387528865875332083814206171776691473035982534904287554687311595628638823537875937519577818577805321712268066130019278766111959092164201989380952572010654858632788659361533818279682303019520353018529689957736225994138912497217752834791315155748572424541506959508295331168617278558890750983817546374649393192550604009277016711390098488240128583616035637076601047101819429555961989467678374494482553797747268471040475346462080466842590694912933136770289891521047521620569660240580381501935112533824300355876402474964732639141992726042699227967823547816360093417216412199245863150302861829745557067498385054945885869269956909272107975093029553211653449872027559602364806654991198818347977535663698074265425278625518184175746728909777727938000816470600161452491921732172147723501414419735685481613611573525521334757418494684385233239073941433345477624168625189835694855620992192221842725502542568876717904946016534668049886272327917860857843838279679766814541009538837863609506800642251252051173929848960841284886269456042419652850222106611863067442786220391949450471237137869609563643719172874677646575739624138908658326459958133904780275900994657640789512694683983525957098258226205224894077267194782684826014769909026401363944374553050682034962524517493996514314298091906592509372216964615157098583874105978859597729754989301617539284681382686838689427741559918559252459539594310499725246808459872736446958486538367362226260991246080512438843904512441365497627807977156914359977001296160894416948685558484063534220722258284886481584560285060168427394522674676788952521385225499546667278239864565961163548862305774564980355936345681743241125150760694794510965960940252288797108931456691368672287489405601015033086179286809208747609178249385890097149096759852613655497818931297848216829989487226588048575640142704775551323796414515237462343645428584447952658678210511413547357395231134271661021359695362314429524849371871101457654035902799344037420073105785390621983874478084784896833214457138687519435064302184531910484810053706146806749192781911979399520614196634287544406437451237181921799983910159195618146751426912397489409071864942319615679452080951465502252316038819301420937621378559566389377870830390697920773467221825625996615014215030680384477345492026054146659252014974428507325186660021324340881907104863317346496514539057962685610055081066587969981635747363840525714591028970641401109712062804390397595156771577004203378699360072305587631763594218731251471205329281918261861258673215791984148488291644706095752706957220917567116722910981690915280173506712748583222871835209353965725121083579151369882091444210067510334671103141267111369908658516398315019701651511685171437657618351556508849099898599823873455283316355076479185358932261854896321329330898570642046752590709154814165498594616371802709819943099244889575712828905923233260972997120844335732654893823911932597463667305836041428138830320382490375898524374417029132765618093773444030707469211201913020330380197621101100449293215160842444859637669838952286847831235526582131449576857262433441893039686426243410773226978028073189154411010446823252716201052652272111660396665573092547110557853763466820653109896526918620564769312570586356620185581007293606598764861179104533488503461136576867532494416680396265797877185560845529654126654085306143444318586769751456614068007002378776591344017127494704205622305389945613140711270004078547332699390814546646458807972708266830634328587856983052358089330657574067954571637752542021149557615814002501262285941302164715509792592309907965473761255176567513575178296664547791745011299614890304639947132962107340437518957359614589019389713111790429782856475032031986915140287080859904801094121472213179476477726224142548545403321571853061422881375850430633217518297986622371721591607716692547487389866549494501146540628433663937900397692656721463853067360965712091807638327166416274888800786925602902284721040317211860820419000422966171196377921337575114959501566049631862947265473642523081770367515906735023507283540567040386743513622224771589150495309844489333096340878076932599397805419341447377441842631298608099888687413260472156951623965864573021631598193195167353812974167729478672422924654366800980676928238280689964004824354037014163149658979409243237896907069779422362508221688957383798623001593776471651228935786015881617557829735233446042815126272037343146531977774160319906655418763979293344195215413418994854447345673831624993419131814809277771038638773431772075456545322077709212019051660962804909263601975988281613323166636528619326686336062735676303544776280350450777235547105859548702790814356240145171806246436267945612753181340783303362542327839449753824372058353114771199260638133467768796959703098339130771098704085913374641442822772634659470474587847787201927715280731767907707157213444730605700733492436931138350493163128404251219256517980694113528013147013047816437885185290928545201165839341965621349143415956258658655705526904965209858033850722426482939728584783163057777560688876446248246857926039535277348030480290058760758251047470916439613626760449256274204208320856611906254543372131535958450687724602901618766795240616342522577195429162991930645537799140373404328752628889639958794757291746426357455254079091451357111369410911939325191076020825202618798531887705842972591677813149699009019211697173727847684726860849003377024242916513005005168323364350389517029893922334517220138128069650117844087451960121228599371623130171144484640903890644954440061986907548516026327505298349187407866808818338510228334508504860825039302133219715518430635455007668282949304137765527939751754613953984683393638304746119966538581538420568533862186725233402830871123282789212507712629463229563989898935821167456270102183564622013496715188190973038119800497340723961036854066431939509790190699639552453005450580685501956730229219139339185680344903982059551002263535361920419947455385938102343955449597783779023742161727111723643435439478221818528624085140066604433258885698670543154706965747458550332323342107301545940516553790686627333799585115625784322988273723198987571415957811196358330059408730681216028764962867446047746491599505497374256269010490377819868359381465741268049256487985561453723478673303904688383436346553794986419270563872931748723320837601123029911367938627089438799362016295154133714248928307220126901475466847653576164773794675200490757155527819653621323926406160136358155907422020203187277605277219005561484255518792530343513984425322341576233610642506390497500865627109535919465897514131034822769306247435363256916078154781811528436679570611086153315044521274739245449454236828860613408414863776700961207151249140430272538607648236341433462351897576645216413767969031495019108575984423919862916421939949072362346468441173940326591840443780513338945257423995082965912285085558215725031071257012668302402929525220118726767562204154205161841634847565169998116141010029960783869092916030288400269104140792886215078424516709087000699282120660418371806535567252532567532861291042487761825829765157959847035622262934860034158722980534989650226291748788202734209222245339856264766914905562842503912757710284027998066365825488926488025456610172967026640765590429099456815065265305371829412703369313785178609040708667114965583434347693385781711386455873678123014587687126603489139095620099393610310291616152881384379099042317473363948045759314931405297634757481193567091101377517210080315590248530906692037671922033229094334676851422144773793937517034436619910403375111735471918550464490263655128162288244625759163330391072253837421821408835086573917715096828874782656995995744906617583441375223970968340800535598491754173818839994469748676265516582765848358845314277568790029095170283529716344562129640435231176006651012412006597558512761785838292041974844236080071930457618932349229279650198751872127267507981255470958904556357921221033346697499235630254947802490114195212382815309114079073860251522742995818072471625916685451333123948049470791191532673430282441860414263639548000448002670496248201792896476697583183271314251702969234889627668440323260927524960357996469256504936818360900323809293459588970695365349406034021665443755890045632882250545255640564482465151875471196218443965825337543885690941130315095261793780029741207665147939425902989695946995565761218656196733786236256125216320862869222103274889218654364802296780705765615144632046927906821207388377814233562823608963208068222468012248261177185896381409183903673672220888321513755600372798394004152970028783076670944474560134556417254370906979396122571429894671543578468788614445812314593571984922528471605049221242470141214780573455105008019086996033027634787081081754501193071412233908663938339529425786905076431006383519834389341596131854347546495569781038293097164651438407007073604112373599843452251610507027056235266012764848308407611830130527932054274628654036036745328651057065874882256981579367897669742205750596834408697350201410206723585020072452256326513410559240190274216248439140359989535394590944070469120914093870012645600162374288021092764579310657922955249887275846101264836999892256959688159205600101655256375678;
#if 0
using cp = std::complex<long double>;
#else
template<typename T>
struct cp_base {
    T m_real, m_imag;
    constexpr cp_base(T r, T i) : m_real(r), m_imag(i) {}
    constexpr cp_base() {}
    constexpr cp_base(T r) : m_real(r), m_imag(0) {}
    constexpr cp_base operator+(const cp_base &o) const {
        return cp_base(m_real + o.m_real, m_imag + o.m_imag);
    }
    constexpr cp_base operator-(const cp_base &o) const {
        return cp_base(m_real - o.m_real, m_imag - o.m_imag);
    }
    constexpr cp_base operator*(const cp_base &o) const {
        return cp_base(m_real * o.m_real - m_imag * o.m_imag, 
                  m_real * o.m_imag + m_imag * o.m_real);
    }
    constexpr cp_base operator+=(const cp_base &o) {
        return *this = *this + o;
    }
    constexpr cp_base operator-=(const cp_base &o) {
        return *this = *this - o;
    }
    constexpr cp_base operator*=(const cp_base &o) {
        return *this = *this * o;
    }
    constexpr cp_base conj() const {return cp_base(m_real, -m_imag); }
    constexpr T real() const {return m_real; }
    constexpr T imag() const {return m_imag; }
    constexpr T& real() {return m_real; }
    constexpr T& imag() {return m_imag; }
};
using cp = cp_base<long double>;
#endif
int n, len;
vector<int> rev;
inline constexpr int fpow(int base, int power, const int& mod) {
    int ans = 1;
    for (; power; base = 1ll * base * base % mod, power >>= 1) 
        if (power & 1) ans = 1ll * ans * base % mod;
    return ans;
}
inline void init() {
    int x = 0;
    for (len = 1; (len <<= 1) < n; x++);
    len <<= 1;
    rev.clear();
    rev.resize(len);
    for (int i = 1; i < len; i++)
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << x);
}
inline void init(int l) {
    rev.clear();
    rev.resize(l);
    for (int i = 1; i < l; i++) {
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (l >> 1));
    }
}
inline void FFT(vector<cp>& a, int n, int type)
{
    for (int i = 0; i < n; ++i)
        if (i < rev[i])
            std::swap(a[i], a[rev[i]]);
    for (int i = 1; i < n; i <<= 1)
    {
        cp wn(std::cos(pi / i), type * std::sin(pi / i));
        for (int j = 0; j < n; j += (i << 1))
        {
            cp w0(1);
            for (int k = 0; k < i; ++k, w0 *= wn)
            {
                cp x = a[j + k], y = w0 * a[i + j + k];
                a[j + k] = x + y;
                a[i + j + k] = x - y;
            }
        }
    }
}
inline void mul(int n, int m, const int& p, vector<int> a, vector<int> b, vector<int>& c) {
    static cp da, db, dc, dd, rel(0.5, 0), img(0, -0.5);
    static const int up = 1 << 15;
    static int v1, v2, v3;
    int len = 1;
    while (len < n + m) len <<= 1;
    a.resize(len);
    b.resize(len);
    rev.clear();
    rev.resize(len);
    for (int i = 1; i < len; i++) {
    	rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (len >> 1));
	}
    for (int i = 0; i < len; i++) {
        a[i] = i < n ? (a[i] % p + p) % p : 0;
        b[i] = i < m ? (b[i] % p + p) % p : 0;
    }
    vector<cp> P(len, cp(0, 0)), Q(len, cp(0, 0)), R(len, cp(0, 0));
    for (int i = 0; i < len; i++) {
        P[i] = cp(a[i] >> 15, a[i] & 32767);
        Q[i] = cp(b[i] >> 15, b[i] & 32767);
    }
    FFT(P, len, 1);
    FFT(Q, len, 1);
    for (int i = 0; i < len; i++) {
        R[i] = P[(len - i) & (len - 1)].conj();
    }
    for (int i = 0; i < len; i++) {
        auto x = P[i];
        auto y = R[i];
        P[i] = (x + y) * rel;
        R[i] = (x - y) * img;
    }
    for (int i = 0; i < len; i++) {
        P[i] = P[i] * Q[i];
        Q[i] = R[i] * Q[i];
    }
    FFT(P, len, -1);
    FFT(Q, len, -1);
    c.clear();
    c.resize(len);
    for (int i = 0; i < len; i++) {
        v1 = (int)(P[i].real() / len + 0.5);
        v2 = (int)(P[i].imag() / len + 0.5) + (int)(Q[i].real() / len + 0.5);
        v3 = (int)(Q[i].imag() / len + 0.5);
        c[i] = 1ll * v1 * up % p * up % p + 1ll * v2 * up % p + v3 % p;
        c[i] = (c[i] % p + p) % p;
    }
}

static vector<int> fac, mfac, invfac, minvfac, inv, minv;

inline void init(int n, int m, const int &p) {
    int tmp = (n << 1) | 1;
    fac.resize(tmp + 1);
    mfac.resize(tmp + 1);
    invfac.resize(tmp + 1);
    minvfac.resize(tmp + 1);
    inv.resize(tmp + 1);
    minv.resize(tmp + 1);
    fac[0] = mfac[0] = 1;

    for (int i = 1; i <= tmp; i++) {
        fac[i] = 1ll * fac[i - 1] * i % p;
        mfac[i] = 1ll * mfac[i - 1] * (m - n + i - 1 + p) % p;
    }

    invfac[tmp] = fpow(fac[tmp], p - 2, p);
    minvfac[tmp] = fpow(mfac[tmp], p - 2, p);

    for (int i = tmp; i; i--) {
        invfac[i - 1] = 1ll * invfac[i] * i % p;
        minvfac[i - 1] = 1ll * minvfac[i] * (m - n + i - 1 + p) % p;
        inv[i] = 1ll * invfac[i] * fac[i - 1] % p;
        minv[i] = 1ll * minvfac[i] * mfac[i - 1] % p;
    }

    minv[0] = 1;
}

inline void LagrangeInterpolation_ex(int n, int m, const int &p, vector<int> a, vector<int> &b) {
    vector<int> f, g;
    int len = 1;
    while (len < n * 3ll + 2) len <<= 1;
    rev.clear();
    rev.resize(len);
    a.resize(len);
    f.resize(len);
    g.resize(len);
    init(n, m, p);
    rev.clear();
    rev.resize(len);
    for (int i = 1; i < len; i++) {
    	rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (len >> 1));
	}

    for (int i = 0; i <= n; i++) {
        f[i] = 1ll * invfac[i] * invfac[n - i] % p * a[i] % p;

        if ((n - i) & 1) {
        	f[i] = p - f[i];
		}
    }

    for (int i = 0; i <= (n << 1); i++) {
        g[i] = minv[i + 1];
    }
// n + 1, (n << 1) + 1
    mul(n + 1, (n << 1) + 1, p, f, g, f);
	b.clear();
	b.resize(n + 1);
    for (int i = n; i <= (n << 1); i++) {
        b[i - n] = 1ll * mfac[i + 1] * minvfac[i - n] % p * f[i] % p;
    }
}
/*

signed main() {
	int n, m;
	vector<int> a, b;
	scanf("%lld%lld", &n, &m);
	a.resize(n + 1);
	for (int i = 0; i <= n; i++) scanf("%lld", &a[i]);
	LagrangeInterpolation_ex(n, m, 998244353, a, b);
	for (int i = 0; i <= n; i++) printf("%lld ", b[i]);
	return 0;
}

*/

inline int solve(int n, const int &p) {
	static vector<int> f, fd, st;
	st.resize(log2(n) + 5);
	f.resize(2);
	int top = 0;
	int s = n;
	while (n) {
		st[++top] = n;
		n >>= 1;
	}
	n = st[top--];
	f[0] = 1;
	f[1] = s + 1;
	while (top--) {
		f.resize(f.size() << 1);
		LagrangeInterpolation_ex(n, n + 1, p, f, fd);
		std::copy(fd.begin(), fd.end(), f.begin() + n + 1);
		f[n << 1 | 1] = 0;
		int tmp = 1ll * n * fpow(s, p - 2, p) % p;
		n <<= 1;
		LagrangeInterpolation_ex(n, tmp, p, f, fd);
		for (int i = 0; i <= n; i++) {
			f[i] = 1ll * f[i] * fd[i] % p;
		}
		if (!(st[top + 1] & 1)) continue;
		for (int i = 0; i <= n; i++) {
			f[i] = 1ll * f[i] * (1ll * s * i % p + n + 1) % p;
		}
		f[++n] = 1;
		for (int i = 1; i <= n; i++) {
			f[n] = 1ll * f[n] * (1ll * s * n % p + i) % p;
		}
	}
	int res = f[0];
	for (int i = 1; i < s; i++) {
		res = 1ll * res * f[i] % p;
	}
	return res;
}
inline int factorial(int n, const int &p) {
	int tn = p - 1 - n;
	int res = 0;
	if (tn <= n) {
		res = fpow(factorial(tn, p), p - 2, p);
		return (tn & 1) ? res : p - res;
	}
	int k = sqrt(n);
	res = solve(k, p);
	for (int i = k * k + 1; i <= n; i++) {
		res = 1ll * res * i % p;
	}
	return res % p;
}
signed main() {
	int T, n, p;
	cin >> T;
	while (T--) {
		cin >> n >> p;
		cout << factorial(n, p) << endl;
	}
}