#define MOD_TYPE 2

#include <bits/stdc++.h>
using namespace std;

#if 1
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif

#if 0
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template <typename T>
using extset =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif

#if 0
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using Int = boost::multiprecision::cpp_int;
using lld = boost::multiprecision::cpp_dec_float_100;
#endif

#pragma region Macros

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
template <typename T>
using smaller_queue = priority_queue<T, vector<T>, greater<T>>;

constexpr ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
constexpr int INF = (int)1e9 + 10;
constexpr ll LINF = (ll)4e18;
const double PI = acos(-1.0);
constexpr double EPS = 1e-11;
constexpr int Dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0};
constexpr int Dy[] = {1, -1, 0, 0, -1, -1, 1, 1, 0};

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define REPI(i, m, n) for (int i = m; i < (int)(n); ++i)
#define repi(i, n) REPI(i, 0, n)
#define YES(n) cout << ((n) ? "YES" : "NO") << "\n"
#define Yes(n) cout << ((n) ? "Yes" : "No") << "\n"
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << "\n";
#define UNIQUE(v) v.erase(unique(all(v)), v.end())

struct io_init {
  io_init() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << setprecision(30) << setiosflags(ios::fixed);
  };
} io_init;
template <typename T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
inline ll floor(ll a, ll b) {
  if (b < 0) a *= -1, b *= -1;
  if (a >= 0) return a / b;
  return -((-a + b - 1) / b);
}
inline ll ceil(ll a, ll b) { return floor(a + b - 1, b); }
template <typename A, size_t N, typename T>
inline void Fill(A (&array)[N], const T &val) {
  fill((T *)array, (T *)(array + N), val);
}
template <typename T>
vector<T> compress(vector<T> &v) {
  vector<T> val = v;
  sort(all(val)), val.erase(unique(all(val)), val.end());
  for (auto &&vi : v) vi = lower_bound(all(val), vi) - val.begin();
  return val;
}
template <typename T, typename U>
constexpr istream &operator>>(istream &is, pair<T, U> &p) noexcept {
  is >> p.first >> p.second;
  return is;
}
template <typename T, typename U>
constexpr ostream &operator<<(ostream &os, pair<T, U> p) noexcept {
  os << p.first << " " << p.second;
  return os;
}
template <typename T>
constexpr istream &operator>>(istream &is, vector<T> &v) noexcept {
  for (int i = 0; i < v.size(); i++) is >> v[i];
  return is;
}
template <typename T>
constexpr ostream &operator<<(ostream &os, vector<T> &v) noexcept {
  for (int i = 0; i < v.size(); i++)
    os << v[i] << (i + 1 == v.size() ? "" : " ");
  return os;
}
template <typename T>
constexpr void operator--(vector<T> &v, int) noexcept {
  for (int i = 0; i < v.size(); i++) v[i]--;
}

random_device seed_gen;
mt19937_64 engine(seed_gen());

#pragma endregion

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

constexpr ll umekomi[] = {0,7600457,30397485,68394315,121590395,189980089,273571773,372365937,486345715,615533953,759924263,919492621,1094277505,1284261215,1489425819,1709799245,1945400165,2196146239,2462103829,2743290025,3039650753,3351211987,3677987867,4019930023,4377098665,4749468157,5136988725,5539755327,5957720031,6390840133,6839204027,7302770941,7781474123,8275425501,8784602677,9308896299,9848446267,10403218281,10973119597,11558220619,12158598917,12774092847,13404831445,14050776781,14711865643,15388194445,16079712169,16786402047,17508329291,18245481283,18997748543,19765267053,20548008117,21345872369,22158969143,22987331157,23830768963,24689453255,25563419637,26452482463,27356748483,28276272973,29210923797,30160826181,31125966023,32106186521,33101694809,34112390485,35138200379,36179290783,37235607123,38307043625,39393721051,40495687441,41612645735,42744948115,43892477939,45054985791,46232918759,47426037995,48634207309,49857644377,51096404425,52350134981,53619237565,54903539347,56202953459,57517590693,58847454067,60192435907,61552643223,62928163903,64318723779,65724584277,67145711075,68581815335,70033240847,71499977679,72981656485,74478759141,75991039675,77518367913,79060953399,80618896467,82191799955,83780010855,85383523301,87002061017,88635886235,90284888989,91949005039,93628464151,95323083863,97032827811,98757787365,100498136137,102253347209,104024022889,105809918237,107610726967,109426976721,111258415739,113104916297,114966646077,116843760409,118735862701,120643218537,122565883729,124503548345,126456516147,128424788117,130407980053,132406616309,134420431033,136449267065,138493474897,140552944927,142627389285,144717162695,146822221041,148942189539,151077614551,153228244333,155393874161,157574791521,159770986595,161982224459,164208764021,166450642565,168707425583,170979629893,173267066637,175569436425,177887174895,180220225265,182568130849,184931499247,187310217363,189703701285,192112661421,194536947223,196976058205,199430538751,201900453037,204385250463,206885205431,209400739121,211931078693,214476805833,217037767685,219613801853,222205089239,224811625977,227433179825,230070121307,232722311473,235389403827,238072038399,240769767131,243482412857,246210582787,248954080579,251712276989,254486009267,257274993307,260079015087,262898173125,265732730955,268582307087,271447184283,274327399259,277222471883,280132992121,283058700851,285999417123,288955529647,291926889519,294913037167,297914794719,300931871121,303963552391,307010872483,310073555483,313150986671,316243744055,319352032621,322475127627,325613455589,328767227165,331935869863,335119942897,338319332847,341533602363,344763166941,348008166167,351267947679,354543253283,357833718989,361139182953,364460085077,367796225331,371147120641,374513546917,377895383043,381291937469,384703971257,388131401491,391573689661,395031154171,398504226479,401991866599,405495069819,409013719877,412547015171,416095902445,419659963793,423238934693,426833415083,430443024969,434067651837,437707790291,441363018431,445033121797,448718769877,452419779227,456135478193,459866612443,463613222397,467374478181,471151175973,474943398963,478750376535,482572608219,486410491741,490262949443,494130926045,498014183127,501912281869,505826007259,509754759025,513698482243,517657768067,521632258785,525621469035,529626148213,533646407673,537681131679,541731501579,545797418797,549877847121,553973688853,558085057931,562211216129,566352675773,570509563283,574681169071,578868417793,583070787495,587288079201,591520838685,595768940129,600031796909,604310119663,608603818889,612912261661,617236170211,621575432097,625929466137,630298964961,634683984961,639083602501,643498578601,647929051067,652374311567,656835103403,661311161545,665801985051,670308312765,674829776455,679366138793,683918138109,688485394113,693067464977,697664978005,702277821939,706905314569,711548519465,716206981121,720880108299,725568854721,730272960695,734991685725,739725743899,744475621043,749239945071,754019826679,758815060187,763624993895,768450553823,773291206131,778146879275,783017851309,787904358777,792805484713,797722108823,802654193115,807600933381,812563174217,817540938299,822533105259,827540887401,832564336595,837602147017,842655471325,847724357361,852807937921,857906901475,863021421243,868150541649,873295328201,878455036771,883629660099,888820129205,894025441759,899245959885,904481679151,909733201977,914998811171,920280272673,925577178583,930888538087,936215528927,941558084255,946914977343,952287518707,957675637061,963078151339,968496517413,973930095291,979378443297,984842349899,990321365055,995815198209,1001324485703,1006849294285,1012388797717,1017943710933,1023514314673,1029099176999,1034699647963,1040315853989,1045946333925,1051592640593,1057254260519,1062930343109,1068621967439,1074329165151,1080051063511,1085788396057,1091541190413,1097308571349,1103091700601,1108889876203,1114702960067,1120531456673,1126375353757,1132233960123,1138108053459,1143997887601,1149901871425,1155821679397,1161756954579,1167706461139,1173671926437,1179652827005,1185648077119,1191658910959,1197685422397,1203726396889,1209782787795,1215854699277,1221941333917,1228043441361,1234160859499,1240292987149,1246440849993,1252604006359,1258781489493,1264975008303,1271183656597,1277406949725,1283645973379,1289900372011,1296169180869,1302453772105,1308753825889,1315068323907,1321398088683,1327743606625,1334103866127,1340479370929,1346870600657,1353276309709,1359697737715,1366134238557,1372585505301,1379052511143,1385534891577,1392031492823,1398544240843,1405072289761,1411614403639,1418172633305,1424746270847,1431334156733,1437937802475,1444557145169,1451190836999,1457839711475,1464504621869,1471183817157,1477878663133,1484588942231,1491313902535,1498054327075,1504810059487,1511580535213,1518366663015,1525168046243,1531984227915,1538815890647,1545662907209,1552524277375,1559401630535,1566294496243,1573201510041,1580124482469,1587062590229,1594015559841,1600983834567,1607967744259,1614966234321,1621980161835,1629009728479,1636053663113,1643113454601,1650188458929,1657277979447,1664383008261,1671503669433,1678638770835,1685789779121,1692956217377,1700136630807,1707333230875,1714545143267,1721771423989,1729013241049,1736270952551,1743542888505,1750830388455,1758133340523,1765451063559,1772784070729,1780132866677,1787496025481,1794874567355,1802268849039,1809677614531,1817102164039,1824541790169,1831996136807,1839466323703,1846951851307,1854451330995,1861967044681,1869498134333,1877043443345,1884604762637,1892181496929,1899772752247,1907378968965,1915001439363,1922638127237,1930290439631,1937958471907,1945640414689,1953338503649,1961051806057,1968779676371,1976523150081,1984282279693,1992055604055,1999845003061,2007649595989,2015468723079,2023303302001,2031153708389,2039018320025,2046898367431,2054794341947,2062704629187,2070630340999,2078571880423,2086527792811,2094499050379,2102486340129,2110487550899,2118504862099,2126537301531,2134584035547,2142647074627,2150725176245,2158817672419,2166926174815,2175049963837,2183188014711,2191342126715,2199511458075,2207695047767,2215894604263,2224109827861,2232338990751,2240584008261,2248844874515,2257119393865,2265410176317,2273716489105,2282037180903,2290373424063,2298725024271,2307091098139,2315473002509,2323870304961,2332282154875,2340709716707,2349152728943,2357610058483,2366083047899,2374571771445,2383074538029,2391593171397,2400127571839,2408675954783,2417239845047,2425819850291,2434414043501,2443023940239,2451649345871,2460289099731,2468944428221,2477615018511,2486300346085,2495001518879,2503717862109,2512448878223,2521195651605,2529958075519,2538733876801,2547526384451,2556334502517,2565156314961,2573994182379,2582847603933,2591715250665,2600598277485,2609497477509,2618410678855,2627339657459,2636284169037,2645243077499,2654217984203,2663207829397,2672212164995,2681232679757,2690268270571,2699318083629,2708383969667,2717465503997,2726560992611,2735672422965,2744799640531,2753940495299,2763097665057,2772269974861,2781456880795,2790659281853,2799877185087,2809109780019,2818357917147,2827621890803,2836899678011,2846193774665,2855502684159,2864826440097,2874165728485,2883520483213,2892889835163,2902274720505,2911675494113,2921089977321,2930520476897,2939966733551,2949426939721,2958903144161,2968395167465,2977901041957,2987422285677,2996959935987,3006511095279,3016078704877,3025661581453,3035258910215,3044872022075,3054500133777,3064142753845,3073801640909,3083475461125,3093163511731,3102867843867,3112587580899,3122321464741,3132070942995,3141836851249,3151615958137,3161411548575,3171222264821,3181047428751,3190888028103,3200744702757,3210615549917,3220501700247,3230403845017,3240320160845,3250252620485,3260199597895,3270161588439,3280139575025,3290132814581,3300140137223,3310163324445,3320202652473,3330255303491,3340324128823,3350408979185,3360507297161,3370621792553,3380752088659,3390896253061,3401056372045,3411231893145,3421421908597,3431627214811,3441848529889,3452084161577,3462335245313,3472602111087,3482883018091,3493179863123,3503492510559,3513819054163,3524161260689,3534519672617,3544891607243,3555279658523,3565683273949,3576101176793,3586534829525,3596984195741,3607447539929,3617926578011,3628421446961,3638930299971,3649455190981,3659995520711,3670550343901,3681120723355,3691706606969,3702306653709,3712922724415,3723554502571,3734200065259,3744862185633,3755539281429,3766229902261,3776937875985,3787660351445,3798397094475,3809150005993,3819918871377,3830701083275,3841498964403,3852313506991,3863141700111,3873985331405,3884845085657,3895718840773,3906608399105,3917513491181,3928432841299,3939368074591,3950318818467,3961283843705,3972264704939,3983261036061,3994271162483,4005297791325,4016339996537,4027395803975,4038467654833,4049555547739,4060657151347,4071774511189,4082907702783,4094054944805,4105218194817,4116397261797,4127589874985,4138798982453,4150022857291,4161261257615,4172515684739,4183785659945,4195069432763,4206369900281,4217685446961,4229014989695,4240360399041,4251721717129,4263096645939,4274487647779,4285894824999,4297315750781,4308752015489,4320204346351,4331671013025,4343153290763,4354651267863,4366163151761,4377691118669,4389234441001,4400792056119,4412366002039,4423954814015,4435558269263,4447177280845,4458812276663,4470460435515,4482125695083,4493806004619,4505500059807,4517210478749,4528936420385,4540676432179,4552431822099,4564203875791,4575989062027,4587790550539,4599608137691,4611439221481,4623286464395,4635148814379,4647025057051,4658918207921,4670826541559,4682748716313,4694687215421,4706641116783,4718609128519,4730592854763,4742592704157,4754605802453,4766635118899,4778680360771,4790739653701,4802814485307,4814905284211,4827010306725,4839130355497,4851267084183,4863417247759,4875583863847,4887765347493,4899960979331,4912173371971,4924400407875,4936641973509,4948899651057,4961172532763,4973459449089,4985762676195,4998081332263,5010413979425,5022762275063,5035127268243,5047505418785,5059898936431,5072309126127,5084732891627,5097172888567,5109628417099,5122097926731,5134583543095,5147084464553,5159599167065,5172130328241,5184676869181,5197237712919,5209814181027,5222406667511,5235012713379,5247634715675,5260272863659,5272924575529,5285592320447,5298276105455,5310973210561,5323686186277,5336415500261,5349158545315,5361917706357,5374692414665,5387480867143,5400285908871,5413105360147,5425939786481,5438789900251,5451655922101,5464535544579,5477431244153,5490342885187,5503267908025,5516209262131,5529166801279,5542137528811,5555124417669,5568127627195,5581143900535,5594175892537,5607224384617,5620286110635,5633364735101,5646458459391,5659566135801,5672690091401,5685829208277,5698982890649,5712152221433,5725336884247,5738535715659,5751750797625,5764981589241,5778225878927,5791486429481,5804763155255,5818052488333,5831358560433,5844680799939,5858016786189,5871367923131,5884735374113,5898116586531,5911513858605,5924927210841,5938353934361,5951797349449,5965255326291,5978727626113,5992216462757,6005720612827,6019238679727,6032772842599,6046323145101,6059885859765,6073465827485,6087061646361,6100670357669,6114295715871,6127937318163,6141591975239,6155262331705,6168949057697,6182649311185,6196365916513,6210098176369,6223844401691,6237606552567,6251384005455,6265175524409,6278983426385,6292806395355,6306643773515,6320496976275,6334366233785,6348248593951,6362147300135,6376062492435,6389990716849,6403935212555,6417895295731,6431869310985,6445859059775,6459865164521,6473884864125,6487920289517,6501971606303,6516036782989,6530117898737,6544214501707,6558325523299,6572452484133,6586594884209,6600751215989,6614923934193,6629112286563,6643313527551,6657531909281,6671765768977,6686012781229,6700276691477,6714556458615,6728849047201,6743158388899,6757483369801,6771822246033,6786176582049,6800547291373,6814932087889,6829332118753,6843748088341,6858177940949,6872624080047,6887085721391,6901561168151,6916052791551,6930560669963,6945081247095,6959618484391,6974171868147,6988737640689,7003320941173,7017919464331,7032531744857,7047159514141,7061804000523,7076461937685,7091136066387,7105825491153,7120529396887,7135248958977,7149983477263,7164733108845,7179497942115,7194279267829,7209073250693,7223884626641,7238711260051,7253551167103,7268407327439,7283279627621,7298165017413,7313067175101,7327985046363,7342916848599,7357863654159,7372827231503,7387804222649,7402797125745,7417806379517,7432828716153,7447867786335,7462922055417,7477990011813,7493074269957,7508174632497,7523288103031,7538418314133,7553564118317,7568723265263,7583898995099,7599090523119,7614294865115,7629516201605,7644752635915,7660003809797,7675270151389,7690552852401,7705848623823,7721161199465,7736489639171,7751831293657,7767189344343,7782562540021,7797949602501,7813352980323,7828772657257,7844205078553,7859654882201,7875119547119,7890597902533,7906092597081,7921603603301,7937127216709,7952667301269,7968223977427,7983793416711,7999378786365,8014980741933,8030596399997,8046227120559,8061874503923,8077535825505,8093212792489,8108905244533,8124611454845,8140334926411,8156072735925,8171824611475,8187593136903,8203377649891,8219174746323,8234988935887,8250818512299,8266661775253,8282521142815,8298396469699,8314285296041,8330189820839,8346111077527,8362045411007,8377996172353,8393962729933,8409942526475,8425938955207,8441950614857,8457975886949,8474018454061,8490076027063,8506146153089,8522234472653,8538337959421,8554454500745,8570587190175,8586736388059,8602898625761,8619077095191,8635271238113,8651479647579,8667703517313,8683943395911,8700197743179,8716466687329,8732752808839,8749051863813,8765367911597,8781698241197,8798043012571,8814404180341,8830780941687,8847171078363,8863577495143,8880000059967,8896435935687,8912888421079,8929355972477,8945837870559,8962335577599,8978849953321,8995376482715,9011919294237,9028478864327,9045051379759,9061640425617,9078245448101,9094863905247,9111498639437,9128148208625,9144811987271,9161492989729,9178188379275,9194897944435,9211623864317,9228365286235,9245120188645,9261891497841,9278679094993,9295479230465,9312296518205,9329129648343,9345976331153,9362837374985,9379716374733,9396608180835,9413516248043,9430440306417,9447377486349,9464331775959,9481300422613,9498283684553,9515283433817,9532298428657,9549326983815,9566371574371,9583432885087,9600506425685,9617597297071,9634704294221,9651823672841,9668959581377,9686112325275,9703277407469,9720458395087,9737656599097,9754867077341,9772094269001,9789337378547,9806594172651,9823867678657,9841156034957,9858458043283,9875776559621,9893110470103,9910458990811,9927822688973,9945202555327,9962595880693,9980005481745,9997431368421,10014869660651,10032325260735,10049796816257,10067281201311,10084781872523,10102298422411,10119828599215,10137375189125,10154937605237,10172513157389,10190105451573,10207712853127,10225334448953,10242972363141,10260625312383,10278292464291,10295976075663,10313675316025,10331386734043,10349116184425,10366860654409,10384618809097,10402393359715,10420184396493,10437987427497,10455806789837,10473643270047,10491492449773,10509357896143,10527239841127,10545135136807,10563045446629,10580972685029,10598913279805,10616870128447,10634842220017,10652828681007,10670831070713,10688849955231,10706880700917,10724928870685,10742993351753,10761070049871,10779163707443,10797273456983,10815396561631,10833534940851,10851690587791,10869858955443,10888043889331,10906244516877,10924457939877,10942688992031,10960934501875,10979194298441,10997470318731,11015762500323,11034067151503,11052389380111,11070726783397,11089077270741,11107444082747,11125827799331,11144223616983,11162636534649,11181065855227,11199507612489,11217965684769,11236439304303,11254927368677,11273431321511,11291951273315,11310484444907,11329034299483,11347598966751,11366177609705,11384773235633,11403384246009,11422008678993,11440649038715,11459306536263,11477975995761,11496662411905,11515364610599,11534079964121,11552811860357,11571560006193,11590320687619,11609097780687,11627891468549,11646698163857,11665521814237,11684360328561,11703213115127,11722081735721,11740966096197,11759863730071,11778777961699,11797708569123,11816651880455,11835611846235,11854588018135,11873576437965,11892582524751,11911604162891,11930638344981,11949689552077,11968757132527,11987837294799,12006933371987,12026045875751,12045172401443,12064313955377,12083472373159,12102643936447,12121832411225,12141035395519,12160252102487,12179485981399,12198734781277,12217997635315,12237276932513,12256572484657,12275879735549,12295205191895,12314545507589,12333899350545,12353269364523,12372655608477,12392055571801,12411470565799,12430902542675,12450347803163,12469808868773,12489286572921,12508777268511,12528284496233,12547807245477,12567342683855,12586895853847,12606464252343,12626045594859,12645644397437,12665259211569,12684885794423,12704529772503,12724189745991,12743862699087,12763552027985,12783257907317,12802976124439,12822710574953,12842461488515,12862225930613,12882006091313,12901803512037,12921612933995,12941439004409,12961280901893,12981136769177,13001008566259,13020895569957,13040796767665,13060714071703,13080647836531,13100594063455,13120557458179,13140536410893,13160528382883,13180537160961,13200561680781,13220598738407,13240652623431,13260723467535,13280806612281,13300906045745,13321022181205,13341150967887,13361296558267,13381457287027,13401631638753,13421823366825,13442029587259,13462249520079,13482486824047,13502739145823,13523005002615,13543286630681,13563585885847,13583895767339,13604223669095,13624568143283,13644924815261,13665297256713,13685687088461,13706089520781,13726507653857,13746943119137,13767391736817,13787856426561,13808336082575,13828829706401,13849340367297,13869866065743,13890404774875,13910961166217,13931533022439,13952117501423,13972718916875,13993336337527,14013966542791,14034613351391,14055277213013,14075952681365,14096644589791,14117353572047,14138074622323,14158813109309,14179566906969,14200334573899,14221118126155,14241917277479,14262729713145,14283559583171,14304404900237,14325263600125,14346138588973,14367029522661,14387933068963,14408853149827,14429790005289,14450739502877,14471705585585,14492687815647,14513683395973,14534693918595,14555722728621,14576762937403,14597820172007,14618892931023,14639979205343,14661083211947,14682201066827,14703333105669,14724481853915,14745645904549,14766823325563,14788017882973,14809228019671,14830450485607,14851690540721,14872946452891,14894214600959,14915499920787,14936801808875,14958115483369,14979445863307,15000793422349,15022152856239,15043529133889,15064922154099,15086327052947,15107749552833,15129187130875,15150638451017,15172105860337,15193588836837,15215086616355,15236599372147,15258129122657,15279671074315,15301229443295,15322804799731,15344391889783,15365996557785,15387617416399,15409250899579,15430900336619,15452566224123,15474245704001,15495941727319,15517652757719,15539377175065,15561119216811,15582875222035,15604645800735,15626432686721,15648235742739,15670051223571,15691883457533,15713732171661,15735593359333,15757471032665,15779366124845,15801271966001,15823195666585,15845135552851,15867087918247,15889056899163,15911042139781,15933040406355,15955055575093,15977086623349,15999129963339,16021190243287,16043266530897,16065355769011,16087461332463,16109584004519,16131718404189,16153870119273,16176038229905,16198218431417,16220415702899,16242629285355,16264854335639,16287097670253,16309356288277,16331628084043,16353915768287,16376220992121,16398538391711,16420872054217,16443221565813,16465585161143,16487964562697,16510359464115,16532767964137,16555192686617,16577634476421,16600088266635,16622559477469,16645046285875,16667545561517,16690061783813,16712594776085,16735139351329,16757701349381,16780280049853,16802870713389,16825477387753,16848101027479,16870737852443,16893390607709,16916059970609,16938742444659,16961441504303,16984154801289,17006882280583,17029627283225,17052387478649,17075160635675,17097950823907,17120757203559,17143574962997,17166411290789,17189262946707,17212127022269,17235007750459,17257905675439,17280815074023,17303741001507,17326684344601,17349639834467,17372612662419,17395600108173,17418601648417,17441620060469,17464653174177,17487700053211,17510763454691,17533843447203,17556935184819,17580044720877,17603169998689,17626307082585,17649462258277,17672633009761,17695816191731,17719017133619,17742233436993,17765462601283,17788707600625,17811969407543,17835244544339,17858535506397,17881843528409,17905163735497,17928501051439,17951853886905,17975220446923,17998602288015,18022000340237,18045412143571,18068840701815,18092285585973,18115741862497,18139216126263,18162706147181,18186208005897,18209727806553,18233263575811,18256811903247,18280376515301,18303957180593,18327551210173,18351161317283,18374788998769,18398428542111,18422084614135,18445756738761,18469441175207,18493143989755,18516861614195,18540591265249,18564340149423,18588102798881,18611878254227,18635671875161,18659481813793,18683303037831,18707141746137,18730996370167,18754864283853,18778746945715,18802647506625,18826560760969,18850489696265,18874436713543,18898395149673,18922370461333,18946361616633,18970365868241,18994387536597,19018423850777,19042473740251,19066540184041,19090623277653,19114718101501,19138830666745,19162958693775,19187099837063,19211257003359,19235430889971,19259618041445,19283820556357,19308040638813,19332272362011,19356521025475,19380786856299,19405064335221,19429358862003,19453669439783,19477992211721,19502333458835,19526688645127,19551057875751,19575443800777,19599845939435,19624260012847,19648690535817,19673138723469,19697598819259,19722075461059,19746568966681,19771075058837,19795596623031,19820135638065,19844686639973,19869254060209,19893839164905,19918435986279,19943050786465,19967679553409,19992321921441,20016981262663,20041656209281,20066344636923,20091050044641,20115770568767,20140503351435,20165254584881,20190021068333,20214800579071,20239595864063,20264409541367,20289233692581,20314074935785,20338933068667,20363803655347,20388690488131,20413594505021,20438510329497,20463442323107,20488391476879,20513352650735,20538331942899,20563326206309,20588333623483,20613357664375,20638398657715,20663450403295,20688519927499,20713606047563,20738704016431,20763819399443,20788951143563,20814095894637,20839255178237,20864432863843,20889622235137,20914829199739,20940051346211,20965286226481,20990539185857,21015806375737,21041087065817,21066385223853,21091698340053,21117024455805,21142368404191,21167727970549,21193099664761,21218488502903,21243894170305,21269310665315,21294744634071,21320195483029,21345659048911,21371138121089,21396635105119,21422143190781,21447668754841,21473211219051,21498765156407,21524336764629,21549924222675,21575523589151,21601140521813,21626773241971,21652419125559,21678081384205,21703760242253,21729450913215,21755158551641,21780883511587,21806619377903,21832372543235,21858142930619,21883925307617,21909723803351,21935539467667,21961366464879,21987212432045,22013073212991,22038946840627,22064837277521,22090742908659,22116661997645,22142598726419,22168550017861,22194514980927,22220496519113,22246494668539,22272504044429,22298531808385,22324575604813,22350630810253,22376703285029,22402792843685,22428893621085,22455011350801,22481146212819,22507293796293,22533457906437,22559637914319,22585831000609,22612040308853,22638264684291,22664503199193,22690758744545,22717028845957,22743313500399,22769613903657,22795932062003,22822259973929,22848606884441,22874969749305,22901344366261,22927736656869,22954144599579,22980565097599,23007001915051,23033456327161,23059921899561,23086404735409,23112904063213,23139416637207,23165945472433,23192489616251,23219046415991,23245621090683,23272211816847,23298814058139,23325434656083,23352071357181,23378719053657,23405384388585,23432066680869,23458759857575,23485471776255,23512199242917,23538938369263,23565694511975,23592467422211,23619253468319,23646054801519,23672874167271,23699705251705,23726553039537,23753415847333,23780292473155,23807186199347,23834095835287,23861018142955,23887956665011,23914912568685,23941879964111,23968865316695,23995865091809,24022878330575,24049908830507,24076956013635,24104014055943,24131089019657,24158182209859,24185286444765,24212407588741,24239545146491,24266695720097,24293863017109,24321045227129,24348241439343,24375454578667,24402682932043,24429923566753,24457181757791,24484456512529,24511742530791,24539046559675,24566367666005,24593698880229,24621049007045,24648415008891,24675793191883,24703186431635,24730598672763,24758022321863,24785461738217,24812919138205,24840388897545,24867875604971,24895377312203,24922891486055,24950423347589,24977971718029,25005531674931,25033109597541,25060703614939,25088308229771,25115931673783,25143571447653,25171222255831,25198890736605,25226576473487,25254273506919,25281987099553,25309716832147,25337460257519,25365220156893,25392995826779,25420784398213,25448590026253,25476411308079,25504244115087,25532096145459,25559963546111,25587842335463,25615738762889,25643652085293,25671576601063,25699518910955,25727477810337,25755448371255,25783436133129,25811440168085,25839456311039,25867489229753,25895539012987,25923600852185,25951679193021,25979775250719,26007882257905,26036006628805,26064147427205,26092300545663,26120470706739,26148657023407,26176855070607,26205072058929,26233303502785,26261547183759,26289808516973,26318086413557,26346375911497,26374682851179,26403006011057,26431341394903,26459693812545,26488063004693,26516444785553,26544841662245,26573256606445,26601682625621,26630126645645,26658586155959,26687058019693,26715547939331,26744052583021,26772570984673,26801106050243,26829657715563,26858220125019,26886800207787,26915397467901,26944006164507,26972631833335,27001275168291,27029930075463,27058600660673,27087288710621,27115989048001,27144706121151,27173440081203,27202185772997,27230949680447,27259726446933,27288518371691,27317326920603,27346151577481,27374988032393,27403843081909,27432712902857,27461595605211,27490494659023,27519410697513,27548338845299,27577283835151,27606246556637,27635219842005,27664210295593,27693217874901,27722236586053,27751273081733,27780326515101,27809390409531,27838472989537,27867570729289,27896681063363,27925808820611,27954953099583,27984109250741,28013281815215,28042472315121,28071673017747,28100892444711,28130127763501,28159374368691,28188638900095,28217919624083,28247213223521,28276521328197,28305848723195,28335186602029,28364542455437,28393914120457,28423298831233,28452700099447,28482116335767,28511546636849,28540993315769,28570455191941,28599931394065,28629423918445,28658932727537,28688452826539,28717991711589,28747546796799,28777111601067,28806694706445,28836295539871,28865907173411,28895535414967,28925181120107,28954839761653,28984513531523,29014205403583,29043908292961,29073629838997,29103364697687,29133113503409,29162880039167,29192661760195,29222456261939,29252267757503,29282096670797,29311935019963,29341792469961,29371666956659,29401552047281,29431453913371,29461374062521,29491305156723,29521252320963,29551217177137,29581193954825,29611188333607,29641198231869,29671220718175,29701260598903,29731315697963,29761383387791,29791469624303,29821569567535,29851682981217,29881814656475,29911961903963,29942120266095,29972296511189,30002490582775,30032694090901,30062915931907,30093154812465,30123404221727,30153671617017,30183955553105,30214251621891,30244564649485,30274894257733,30305236297265,30335594525235,30365968584253,30396356427241};

ll phi(ll n) {
  if (n == 1) return 0;
  ll res = n;
  for (ll i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      res = res / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  }
  if (n > 1) res = res / n * (n - 1);
  return res;
}

const int B = 5000;

void solve() {
  int t;
  cin >> t;
  rep(_, t) {
    ll n;
    cin >> n;
    ll s = umekomi[n / B];
    for (int i = (n / B) * B + 1; i <= n; i++) {
      s += phi(i);
    }
    cout << n * (n - 1) - s << "\n";
  }
}

int main() { solve(); }