結果
| 問題 | No.2249 GCDistance |
| ユーザー |
 stoq
|
| 提出日時 | 2023-03-17 23:15:29 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 51,252 bytes |
| コンパイル時間 | 2,521 ms |
| コンパイル使用メモリ | 205,784 KB |
| 実行使用メモリ | 7,860 KB |
| 最終ジャッジ日時 | 2023-10-18 16:13:53 |
| 合計ジャッジ時間 | 9,585 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge13 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 4 ms
4,348 KB |
| testcase_01 | TLE | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
ソースコード
#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,2736187,10943163,24621517,43772257,68394315,98487145,134047851,175086139,221593049,273571773,331021873,393942527,462332563,536197599,615533953,700335357,790613321,886363353,987592581,1094277505,1206439741,1324076199,1447177167,1575759199,1709799245,1849329415,1994315115,2144772047,2300708497,2462103829,2628998657,2801341013,2979162303,3162451257,3351211987,3545447521,3745143359,3950324211,4160974853,4377098665,4598679949,4825737837,5058274417,5296270233,5539755327,5788695767,6043115831,6303027973,6568370107,6839204027,7115490697,7397279439,7684525297,7977246985,8275425501,8579077413,8888223055,9202807867,9522908391,9848446267,10179483577,10515939173,10857902749,11205328317,11558220619,11916609011,12280457049,12649780225,13024551667,13404831445,13790558169,14181745205,14578420437,14980576025,15388194445,15801266757,16219818581,16643870699,17073342219,17508329291,17948777343,18394699817,18846065569,19302917781,19765267053,20233068507,20706355441,21185061907,21669327547,22158969143,22654134839,23154770457,23660842115,24172443339,24689453255,25212002787,25739972179,26273415493,26812360499,27356748483,27906625071,28461963471,29022802025,29589048245,30160826181,30738043505,31320740205,31908929797,32502556637,33101694809,33706251107,34316308077,34931839875,35552836415,36179290783,36811254171,37448666109,38091540835,38739893487,39393721051,40052988543,40717787919,41388005211,42063753553,42744948115,43431588569,44123714987,44821268151,45524371859,46232918759,46946938341,47666377103,48391358679,49121762017,49857644377,50599048547,51345857747,52098218341,52855953767,53619237565,54387935057,55162114543,55941808223,56726968037,57517590693,58313611697,59115200617,59922220083,60734691285,61552643223,62376119255,63205068489,64039412955,64879256519,65724584277,66575337537,67431641999,68293397067,69160587649,70033240847,70911377093,71795056451,72684114041,73578689161,74478759141,75384277399,76295222393,77211628833,78133619891,79060953399,79993860403,80932179815,81876007911,82825280573,83780010855,84740237871,85705909421,86677115619,87653716733,88635886235,89623414225,90616454657,91614958107,92618963217,93628464151,94643345743,95663824507,96689648797,97720993353,98757787365,99800138503,100847893821,101901131669,102959801447,104024022889,105093668153,106168781141,107249314215,108335419379,109426976721,110523992761,111626454669,112734362535,113847860627,114966646077,116091097041,117220881583,118356223939,119496991501,120643218537,121794914629,122952053001,124114820787,125282908165,126456516147,127635559123,128820099551,130010177311,131205587411,132406616309,133613031733,134824986331,136042330293,137265174893,138493474897,139727248311,140966535551,142211254359,143461504549,144717162695,145978298377,147244902669,148516927369,149794517511,151077614551,152366077049,153660034261,154959457547,156264431809,157574791521,158890627449,160211966001,161538890679,162871058015,164208764021,165552065655,166900620607,168254894423,169614440415,170979629893,172350116921,173726181893,175107702207,176494684731,177887174895,179285098669,180688596319,182097361947,183511688643,184931499247,186356758285,187787546351,189223780121,190665504059,192112661421,193565288191,195023427079,196487000619,197956130757,199430538751,200910607733,202396056145,203886953957,205383413861,206885205431,208392685655,209905469999,211423862539,212947576739,214476805833,216011551481,217551676217,219097355091,220648450551,222205089239,223767139523,225334649529,226907633541,228486087483,230070121307,231659562835,233254508049,234854777429,236460628401,238072038399,239688700847,241311018723,242938733435,244571920677,246210582787,247854756289,249504318969,251159376577,252819925735,254486009267,256157543541,257834456681,259516935955,261204804021,262898173125,264597019835,266301365055,268011199687,269726468585,271447184283,273173411021,274904986435,276642234617,278384829115,280132992121,281886478085,283645520837,285410088021,287179972789,288955529647,290736339695,292522853005,294314637297,296111911071,297914794719,299723077047,301536797333,303356078695,305180847617,307010872483,308846534793,310687630287,312534208807,314386324621,316243744055,318106854567,319975265167,321849178183,323728639417,325613455589,327503805375,329399710797,331300943057,333207725167,335119942897,337037605417,338960741807,340889459835,342823643165,344763166941,346708331535,348658762105,350614773329,352576210347,354543253283,356515684785,358493628587,360476918145,362465683981,364460085077,366459696707,368465106179,370475722353,372492071973,374513546917,376540790231,378573402899,380611429163,382655004079,384703971257,386758561091,388818444821,390883958243,392954824481,395031154171,397112932775,399200397459,401293217439,403391403519,405495069819,407604352299,409718914193,411839188799,413964722547,416095902445,418232447065,420374420849,422522034021,424674819355,426833415083,428997289453,431166741379,433341485271,435521823269,437707790291,439898943587,442095692753,444297774561,446505711687,448718769877,450937314025,453161431817,455390993123,457626209197,459866612443,462112682519,464364129669,466620962971,468883375709,471151175973,473424574739,475703418519,477987758505,480277499505,482572608219,484873391319,487179574563,489491146145,491808283205,494130926045,496459011777,498792525251,501131466617,503475910899,505826007259,508181339219,510542206439,512908496015,515280375909,517657768067,520040271227,522428721147,524822458421,527221736251,529626148213,532036358791,534451948033,536873009643,539299670121,541731501579,544169162491,546612005991,549060612899,551514391803,553973688853,556438596381,558908972361,561384828939,563865896533,566352675773,568844891885,571342418165,573845554879,576354190189,578868417793,581387992907,583912857435,586443452373,588979317827,591520838685,594067873187,596620201703,599178016363,601741269531,604310119663,606884313493,609464009183,612049262077,614640078411,617236170211,619837793281,622445064991,625057408713,627675527177,630298964961,632928063267,635562451519,638202270281,640847746183,643498578601,646155007583,648816742981,651484226477,654156775159,656835103403,659518689807,662207830513,664902487891,667602540031,670308312765,673019277645,675735749377,678457692713,681185248707,683918138109,686656576445,689400453673,692149896793,694904693667,697664978005,700430610619,703201982279,705978608123,708760815509,711548519465,714341426619,717140242339,719944090743,722753873883,725568854721,728389398871,731215197463,734046637321,736883457849,739725743899,742573796947,745426960907,748285898893,751150024655,754019826679,756895057809,759775475955,762661764505,765553518107,768450553823,771353003565,774261063281,777174531103,780093341283,783017851309,785947768981,788883258975,791823957795,794770308781,797722108823,800679320427,803642224105,806610464405,809584104741,812563174217,815547715305,818537926413,821533408267,824534411103,827540887401,830553037889,833570373587,836593279629,839621865517,842655471325,845694909319,848739588897,851790076839,854845692899,857906901475,860973664101,864045738043,867123478249,870206539645,873295328201,876389085863,879488714495,882593679055,885704019509,888820129205,891941441859,895068466469,898200737893,901338347573,904481679151,907630397135,910784784961,913944376683,917109622313,920280272673,923456428415,926638022449,929824935543,933017543589,936215528927,939419207671,942628006461,945842291603,949062057577,952287518707,955518586571,958754693499,961996549621,965243779869,968496517413,971754608491,975018243777,978287494219,981562170581,984842349899,988127598033,991418625527,994715253157,998017106483,1001324485703,1004637376735,1007955966881,1011279660587,1014609147611,1017943710933,1021283941409,1024629707869,1027981030207,1031337782707,1034699647963,1038067311841,1041440491341,1044818894243,1048203019317,1051592640593,1054987618673,1058387985681,1061793703501,1065205291075,1068621967439,1072044499907,1075472087191,1078905477283,1082344250559,1085788396057,1089238316459,1092693097683,1096154002771,1099619990523,1103091700601,1106568582621,1110051146453,1113539139877,1117032509171,1120531456673,1124035825577,1127545881285,1131061110383,1134581811559,1138108053459,1141639908827,1145177169275,1148719871935,1152268070993,1155821679397,1159380672057,1162945301437,1166515356317,1170090829231,1173671926437,1177258443827,1180850371979,1184447736799,1188050735115,1191658910959,1195272800897,1198891982441,1202516863445,1206147255691,1209782787795,1213423971901,1217070479767,1220722705763,1224380364909,1228043441361,1231711795233,1235385950849,1239065395921,1242750111013,1246440849993,1250136673329,1253838284263,1257544809899,1261257150951,1264975008303,1268698024739,1272427010931,1276161105511,1279900942509,1283645973379,1287396691427,1291152675823,1294914061229,1298681179809,1302453772105,1306231736911,1310015029885,1313803716249,1317598402603,1321398088683,1325203591513,1329014373677,1332830755089,1336652359139,1340479370929,1344312249813,1348150287361,1351994022081,1355842943129,1359697737715,1363557553767,1367423165719,1371294211857,1375170479717,1379052511143,1382939920835,1386832833159,1390731226563,1394634793987,1398544240843,1402458943951,1406379101295,1410304840485,1414236121635,1418172633305,1422114570559,1426062210497,1430015243709,1433974085841,1437937802475,1441907451919,1445882199709,1449862586719,1453848490245,1457839711475,1461836578497,1465838913311,1469846846293,1473859905865,1477878663133,1481903000693,1485932591449,1489967688207,1494008066101,1498054327075,1502105789903,1506162745907,1510225220113,1514292864579,1518366663015,1522445419727,1526529993503,1530619586517,1534715021441,1538815890647,1542921901433,1547033973203,1551150960303,1555273743333,1559401630535,1563535342425,1567674398747,1571818725055,1575968889367,1580124482469,1584285462747,1588451722617,1592623761017,1596801142573,1600983834567,1605172028035,1609366027703,1613565364731,1617769852003,1621980161835,1626195875735,1630416895193,1634643671487,1638875795509,1643113454601,1647356461095,1651604563661,1655858843391,1660118117957,1664383008261,1668653485219,1672929530037,1677210671809,1681497389375,1685789779121,1690087373219,1694390726129,1698699254567,1703013813415,1707333230875,1711658252647,1715988821331,1720324728881,1724666457193,1729013241049,1733366103031,1737723503731,1742087161241,1746455897667,1750830388455,1755210192555,1759595530567,1763986334169,1768382315393,1772784070729,1777191180481,1781604018567,1786022067135,1790445706111,1794874567355,1799309273517,1803749184595,1808194688693,1812645472155,1817102164039,1821563877125,1826031270039,1830504246655,1834982319393,1839466323703,1843955101181,1848450208947,1852950216833,1857456024615,1861967044681,1866483491571,1871005660611,1875532997137,1880066510827,1884604762637,1889148718647,1893697997635,1898253080233,1902813340007,1907378968965,1911950407281,1916527357093,1921109678665,1925697234715,1930290439631,1934889236783,1939493092835,1944102945935,1948717918535,1953338503649,1957964605181,1962596083897,1967232978899,1971875193683,1976523150081,1981176776503,1985835710851,1990499781595,1995169647027,1999845003061,2004525625023,2009211743377,2013903445463,2018600771423,2023303302001,2028011302277,2032725028185,2037443720525,2042168567969,2046898367431,2051634244463,2056374941549,2061121182347,2065873312445,2070630340999,2075393336457,2080161521497,2084935570315,2089714436501,2094499050379,2099289401541,2104084875485,2108886039799,2113692559579,2118504862099,2123322157415,2128145043777,2132973540733,2137807580377,2142647074627,2147491890029,2152342321513,2157197895649,2162059330347,2166926174815,2171798072843,2176676208341,2181559157113,2186448129003,2191342126715,2196241463673,2201146505329,2206056901441,2210973175267,2215894604263,2220821627239,2225753887065,2230692010423,2235635097195,2240584008261,2245538604879,2250498119425,2255463626617,2260433936679,2265410176317,2270392035817,2275378927387,2280371693631,2285369702519,2290373424063,2295382225137,2300396886803,2305416712751,2310442266179,2315473002509,2320509438229,2325551579123,2330598635283,2335651459241,2340709716707,2345773187439,2350842362007,2355917341127,2360997487189,2366083047899,2371174038947,2376270769185,2381372619487,2386480166397,2391593171397,2396711868313,2401835560139,2406964765783,2412099844735,2417239845047,2422386009829,2427537141177,2432694050087,2437856177265,2443023940239,2448196905129,2453375499737,2458559663353,2463749223295,2468944428221,2474144672723,2479350844549,2484562075965,2489779158359,2495001518879,2500229289219,2505462834519,2510701827463,2515945968241,2521195651605,2526450838393,2531711597037,2536977734843,2542249374757,2547526384451,2552808938361,2558097044157,2563390498859,2568689507389,2573994182379,2579304401385,2584619603807,2589940239549,2595266788623,2600598277485,2605935796875,2611278659735,2616626805163,2621980487123,2627339657459,2632704420985,2638074323615,2643450216379,2648831173127,2654217984203,2659609542741,2665007079471,2670410362241,2675818347047,2681232679757,2686651676369,2692076718487,2697506870925,2702942799233,2708383969667,2713830480551,2719282937525,2724740900351,2730203854393,2735672422965,2741146332065,2746626094753,2752110706379,2757601373681,2763097665057,2768599014887,2774105921159,2779617966449,2785136208593,2790659281853,2796188294751,2801722339717,2807262332739,2812807243067,2818357917147,2823914079145,2829475670535,2835042867963,2840615328193,2846193774665,2851777075361,2857365949677,2862960513543,2868560268115,2874165728485,2879776357073,2885393103701,2891014853597,2896642018387,2902274720505,2907912725973,2913556880485,2919205710295,2924860548507,2930520476897,2936186292713,2941857323847,2947533724075,2953215776783,2958903144161,2964596446731,2970294561805,2975998330923,2981707637871,2987422285677,2993143132881,2998868515883,3004599975031,3010336644677,3016078704877,3021826561349,3027579004525,3033338003201,3039102089241,3044872022075,3050646674777,3056426989795,3062213229237,3068004517101,3073801640909,3079603594511,3085411698075,3091224755723,3097043794937,3102867843867,3108697323183,3114532822803,3120373697763,3126219697343,3132070942995,3137928361291,3143790888337,3149658772179,3155532269063,3161411548575,3167296011145,3173185797227,3179080884003,3184981861099,3190888028103,3196800002613,3202717315863,3208640094903,3214568162661,3220501700247,3226440910821,3232385358603,3238335871053,3244291127023,3250252620485,3256218609117,3262190682071,3268168577743,3274151008379,3280139575025,3286133164555,3292133034957,3298137489455,3304147654927,3310163324445,3316184720765,3322211343009,3328243364765,3334281415365,3340324128823,3346372906549,3352426678345,3358486228675,3364551381099,3370621792553,3376697839979,3382779197273,3388866013201,3394958550227,3401056372045,3407159426155,3413268374957,3419382275925,3425502357807,3431627214811,3437757804689,3443893855071,3450035852147,3456182898761,3462335245313,3468493455395,3474656738199,3480825772207,3486999722397,3493179863123,3499365388259,3505556386837,3511752289087,3517954100531,3524161260689,3530374019761,3536592442497,3542815734265,3549045177313,3555279658523,3561519869455,3567765483335,3574016129239,3580272731069,3586534829525,3592802326189,3599074961219,3605353407503,3611637247481,3617926578011,3624221428795,3630521760841,3636827937071,3643138532713,3649455190981,3655777316217,3662104676959,3668438141699,3674776702597,3681120723355,3687469984291,3693824941661,3700185641619,3706551248997,3712922724415,3719299845801,3725682242347,3732069666777,3738462772637,3744862185633,3751265864459,3757675609991,3764090560401,3770511685971,3776937875985,3783368947031,3789806100969,3796248386795,3802696898539,3809150005993,3815609459927,3822073262571,3828543269505,3835018471533,3841498964403,3847985580193,3854477305347,3860974905701,3867477446997,3873985331405,3880499115407,3887018501677,3893542903011,3900073051545,3906608399105,3913149461769,3919695876755,3926247700825,3932804962535,3939368074591,3945936276135,3952510553511,3959089445071,3965674079135,3972264704939,3978859949255,3985461626129,3992067992119,3998680540763,4005297791325,4011920818301,4018549382813,4025183008787,4031822975707,4038467654833,4045118315573,4051774101165,4058435650885,4065102307293,4071774511189,4078452293581,4085135301971,4091824509289,4098518355195,4105218194817,4111923319155,4118633695067,4125350089819,4132071795153,4138798982453,4145531055735,4152268991007,4159012679261,4165761092805,4172515684739,4179275838481,4186041017953,4192811765177,4199587440637,4206369900281,4213156679001,4219949511241,4226747711319,4233551634471,4240360399041,4247175065839,4253995236251,4260820106721,4267651612295,4274487647779,4281330166439,4288176887111,4295030103891,4301888299051,4308752015489,4315621454457,4322496323329,4329376893741,4336261996615,4343153290763,4350049565543,4356951821789,4363859445023,4370772737725,4377691118669,4384615189905,4391544644611,4398479438357,4405419967039,4412366002039,4419317149223,4426273959907,4433236115285,4440203825345,4447177280845,4454155609755,4461140075483,4468129547381,4475125082049,4482125695083,4489131493373,4496142972391,4503159791615,4510182551763,4517210478749,4524243863219,4531282683725,4538326930105,4545376952655,4552431822099,4559492984573,4566559219625,4573631256853,4580708063147,4587790550539,4594879070665,4601972292561,4609071482087,4616176077391,4623286464395,4630401309193,4637522658421,4644649025481,4651780689503,4658918207921,4666061202633,4673209664269,4680363087133,4687522234349,4694687215421,4701857306259,4709032919559,4716214466325,4723400871623,4730592854763,4737790227805,4744993287061,4752201692471,4759415828381,4766635118899,4773860554271,4781090757033,4788326519463,4795567886727,4802814485307,4810066949971,4817324572821,4824588113543,4831856576193,4839130355497,4846410458195,4853695193843,4860985878459,4868281988335,4875583863847,4882890459635,4890202639163,4897520642037,4904843851661,4912173371971,4919507242039,4926847405031,4934192345277,4941543086831,4948899651057,4956261026143,4963628536215,4971001090309,4978379229781,4985762676195,4993151764931,5000546270865,5007946252215,5015351827279,5022762275063,5030178960005,5037600908861,5045028088959,5052461166981,5059898936431,5067343494339,5074792621115,5082247179757,5089707145593,5097172888567,5104644092979,5112120111063,5119602774837,5127090167653,5134583543095,5142081356927,5149585535603,5157095265031,5164609994973,5172130328241,5179656281221,5187187470509,5194724125291,5202266648789,5209814181027,5217367251127,5224925911543,5232490454415,5240060179191,5247634715675,5255215281433,5262801587815,5270392779077,5277989886951,5285592320447,5293200613251,5300813540899,5308432198389,5316056654545,5323686186277,5331321914149,5338962444175,5346609055435,5354260300129,5361917706357,5369580377781,5377248131009,5384921992811,5392600704051,5400285908871,5407975100077,5415670684181,5423371713047,5431077729435,5438789900251,5446507105303,5454230660647,5461958487225,5469692122403,5477431244153,5485176166425,5492926372657,5500681801715,5508443113181,5516209262131,5523981376525,5531759039167,5539542088993,5547330316823,5555124417669,5562923833725,5570728889039,5578539065107,5586354863773,5594175892537,5602002853067,5609835127789,5617672718739,5625515957341,5633364735101,5641218825037,5649077810803,5656943623823,5664814089581,5672690091401,5680571306345,5688458333419,5696350582633,5704248411203,5712152221433,5720060781163,5727975116705,5735894369357,5743820256345,5751750797625,5759686688477,5767628835519,5775575822525,5783528759185,5791486429481,5799449875421,5807419033561,5815393410261,5823373435653,5831358560433,5839349883623,5847346297381,5855347908999,5863355612849,5871367923131,5879386470121,5887410406401,5895439452333,5903474031329,5911513858605,5919559639739,5927610489131,5935667207733,5943729443609,5951797349449,5959869861657,5967947998543,5976032715767,5984121361113,5992216462757,6000316644537,6008422702481,6016534066729,6024650476823,6032772842599,6040899983741,6049033695377,6057172066889,6065316663865,6073465827485,6081620792973,6089781451005,6097947399849,6106118778169,6114295715871,6122478381849,6130666253295,6138859276971,6147058019287,6155262331705,6163472285007,6171687429121,6179908251779,6188134551615,6196365916513,6204603135581,6212845080105,6221093649035,6229346948697,6237606552567,6245871020989,6254140541251,6262416068747,6270696527395,6278983426385,6287274928531,6295572673169,6303874993731,6312183543177,6320496976275,6328815894925,6337141307789,6345470868265,6353806827485,6362147300135,6370493850871,6378846472737,6387203473393,6395566540885,6403935212555,6412309198661,6420688380111,6429073359671,6437463541209,6445859059775,6454260459677,6462667071473,6471079659657,6479497026541,6487920289517,6496348977893,6504782525491,6513222431149,6521667585331,6530117898737,6538573851627,6547034905245,6555502343081,6563974414043,6572452484133,6580935738151,6589425125345,6597918908429,6606418351239,6614923934193,6623434413765,6631950973461,6640472040573,6648999627499,6657531909281,6666070095357,6674613337023,6683162166529,6691716567239,6700276691477,6708842810663,6717412589043,6725989593141,6734571312069,6743158388899,6751751116259,6760348953429,6768953374111,6777562418753,6786176582049,6794796765773,6803422357183,6812053535833,6820690178977,6829332118753,6837979566931,6846632629275,6855290911965,6863954251819,6872624080047,6881298709495,6889979735837,6898665261763,6907356054945,6916052791551,6924754738561,6933462753611,6942175799027,6950894373443,6959618484391,6968348018295,6977083108669,6985822948953,6994569495845,7003320941173,7012077988203,7020839845639,7029607662935,7038381325571,7047159514141,7055944261005,7064733903119,7073529664605,7082329694921,7091136066387,7099947186507,7108764424191,7117586950687,7126415119723,7135248958977,7144087349127,7152931997971,7161781830323,7170636841617,7179497942115,7188364774419,7197236400363,7206113665973,7214995767075,7223884626641,7232778094535,7241677260155,7250581784325,7259491976467,7268407327439,7277328304867,7286254968389,7295186507515,7304124961515,7313067175101,7322016158821,7330969452003,7339928583293,7348893706049,7357863654159,7366839628099,7375820446325,7384807799553,7393799965603,7402797125745,7411800324131,7420808961993,7429823240061,7438842728447,7447867786335,7456898033249,7465933954887,7474975199073,7484022123833,7493074269957,7502132319847,7511195790295,7520264348019,7529338485723,7538418314133,7547503141441,7556593997007,7565690232685,7574791993933,7583898995099,7593011284377,7602129517095,7611252263041,7620381718777,7629516201605,7638656339127,7647801341647,7656952307723,7666108655149,7675270151389,7684437848907,7693609998187,7702788663381,7711971509855,7721161199465,7730355507883,7739555519499,7748761479093,7757972482405,7767189344343,7776410763539,7785638376299,7794871346673,7804109203493,7813352980323,7822602587881,7831857687745,7841117667003,7850382925557,7859654882201,7868930759999,7878213159989,7887501053807,7896794577609,7906092597081,7915396259775,7924706449217,7934020690765,7943341716561,7952667301269,7961999301529,7971335495331,7980677728231,7990026045681,7999378786365,8008737931639,8018101948077,8027472098837,8036847107707,8046227120559,8055613386213,8065004901171,8074402146975,8083804552147,8093212792489,8102626162129,8112045088627,8121469144535,8130898985149,8140334926411,8149775424125,8159221719051,8168673090577,8178130396991,8187593136903,8197061449145,8206534626273,8216013920963,8225498966577,8234988935887,8244484372761,8253985102901,8263491696219,8273003982633,8282521142815,8292044179645,8301572553127,8311106139599,8320645645387,8330189820839,8339740209101,8349296101647,8358857523369,8368423588897,8377996172353,8387573997373,8397156297683,8406745559641,8416338831349,8425938955207,8435543340139,8445154241103,8454769847037,8464390882875,8474018454061,8483650725337,8493288486937,8502931464185,8512580539579,8522234472653,8531893431673,8541558715453,8551230026167,8560906102465,8570587190175,8580274062725,8589966924007,8599664528559,8609368042619,8619077095191,8628791769179,8638511749219,8648236488111,8657967572089,8667703517313,8677445248331,8687193024897,8696945330153,8706703248005,8716466687329,8726236645939,8736010845589,8745790757087,8755576079927,8765367911597,8775163995849,8784965257289,8794772805871,8804585336661,8814404180341,8824227796737,8834057617131,8843891714575,8853732148263,8863577495143,8873428577457,8883285604553,8893147905853,8903015727289,8912888421079,8922766720913,8932650683773,8942540365001,8952435162931,8962335577599,8972241316803,8982152942425,8992069413455,9001991612459,9011919294237,9021853322129,9031791491249,9041736360265,9051685672221,9061640425617,9071601349335,9081566568771,9091538842847,9101515390473,9111498639437,9121486052185,9131479112677,9141478378537,9151482505123,9161492989729,9171507447639,9181528858067,9191554535621,9201586672405,9211623864317,9221665864089,9231714312803,9241768234595,9251827479389,9261891497841,9271961921277,9282037310959,9292117792445,9302204424775,9312296518205,9322394191203,9332496536265,9342604648879,9352718758621,9362837374985,9372962268741,9383092900677,9393228924173,9403369671955,9413516248043,9423668858015,9433825798415,9443989098407,9454157466519,9464331775959,9474510638099,9484695527945,9494886384383,9505081564293,9515283433817,9525489747483,9535702891339,9545920044685,9556143376483,9566371574371,9576605907305,9586846011081,9597090957725,9607342160141,9617597297071,9627858967469,9638125628293,9648398180447,9658676370373,9668959581377,9679248932967,9689542918229,9699842577141,9710148087809,9720458395087,9730774903509,9741096578309,9751423804699,9761756409583,9772094269001,9782438408107,9792786717493,9803141892231,9813501522743,9823867678657,9834238546523,9844614620995,9854996267795,9865383291259,9875776559621,9886174833711,9896578685403,9906987540719,9917402490935,9927822688973,9938248080919,9948679840135,9959116018233,9969558377583,9980005481745,9990458647743,10000917186397,10011380430255,10021850336281,10032325260735,10042805767829,10053291227617,10063783003085,10074279187597,10084781872523,10095289409345,10105802793263,10116321640919,10126845311789,10137375189125,10147910094227,10158450252939,10168996323745,10179548752267,10190105451573,10200667911773,10211235027267,10221809241649,10232387634411,10242972363141,10253561791713,10264157299075,10274757756107,10285363713153,10295976075663,10306592367073,10317215682607,10327843429941,10338477473753,10349116184425,10359760709323,10370410537739,10381066401993,10391727077811,10402393359715,10413065977769,10423742430409,10434424954831,10445113283439,10455806789837,10466506917261,10477211293737,10487921697691,10498637421181,10509357896143,10520084721117,10530816481687,10541554193081,10552297286989,10563045446629,10573799495879,10584559043931,10595323874169,10606093918783,10616870128447,10627651529827,10638438548089,10649230609143,10660027880797,10670831070713,10681639206095,10692454223175,10703273519693,10714098707071,10724928870685,10735764924967,10746606694969,10757452907943,10768306216033,10779163707443,10790027519357,10800895822431,10811770188081,10822650272899,10833534940851,10844426121573,10855322065805,10866224073247,10877131080201,10888043889331,10898961597863,10909885086605,10920814295557,10931748710571,10942688992031,10953633548353,10964584500245,10975541573967,10986502495179,10997470318731,11008443103427,11019421893961,11030405255341,11041393724139,11052389380111,11063389238917,11074394982105,11085405493107,11096422571319,11107444082747,11118472059541,11129505238163,11140543043613,11151587023029,11162636534649,11173692036941,11184751617443,11195816999823,11206889203471,11217965684769,11229048098207,11240135475585,11251229170989,11262327421547,11273431321511,11284540561787,11295655537671,11306776789955,11317902327141,11329034299483,11340170481701,11351313310569,11362460801087,11373614427375,11384773235633,11395937434811,11407107472179,11418282698007,11429463388689,11440649038715,11451840616033,11463038575197,11474240363091,11485448942249,11496662411905,11507881022403,11519106064581,11530334667043,11541571351221,11552811860357,11564058153173,11575309778935,11586567039023,11597830207569,11609097780687,11620372295137,11631651296475,11642936409325,11654225525627,11665521814237,11676822754599,11688128849091,11699440926411,11710758415695,11722081735721,11733409633773,11744743936403,11756083309277,11767427779295,11778777961699,11790134520523,11801495615643,11812862362685,11824234224007,11835611846235,11846994844681,11858383590677,11869778165893,11881177428245,11892582524751,11903992820133,11915408739987,11926829899725,11938256912289,11949689552077,11961127793909,11972570401399,11984019322459,11995474000831,12006933371987,12018398773931,12029868471383,12041345726639,12052827130717,12064313955377,12075806995681,12087304638803,12098808182389,12110317072589,12121832411225,12133351346033,12144876801675,12156407630527,12167943969797,12179485981399,12191032957233,12202586511161,12214144268245,12225707752777,12237276932513,12248851506729,12260431830231,12272017195393,12283608497615,12295205191895,12306806745787,12318414489267,12330026422815,12341645653235,12353269364523,12364898928615,12376534069121,12388174004029,12399819933347,12411470565799,12423127731467,12434789774521,12446457717483,12458130336821,12469808868773,12481492863321,12493182268217,12504877929087,12516578199683,12528284496233,12539995711461,12551712244233,12563434943499,12575162120783,12586895853847,12598634740017,12610379012613,12622128891509,12633883669065,12645644397437,12657410263099,12669182011343,12680959230117,12692742336839,12704529772503,12716323001501,12728122475481,12739926470431,12751736715959,12763552027985,12775372926833,12787198533525,12799030899353,12810868252333,12822710574953,12834558931849,12846412956019,12858272609759,12870136198591,12882006091313,12893882298779,12905762407599,12917649593259,12929540812757,12941439004409,12953341988735,12965250528801,12977164580787,12989083169697,13001008566259,13012938704781,13024875063545,13036815040417,13048762039395,13060714071703,13072671748743,13084635037577,13096603048227,13108577994467,13120557458179,13132541739773,13144532141583,13156528402793,13168529963517,13180537160961,13192549240049,13204566953133,13216590352503,13228619183911,13240652623431,13252692669411,13264737893585,13276788947011,13288844945745,13300906045745,13312973989413,13325045696701,13337123745015,13349207186349,13361296558267,13373390242179,13385490612813,13397595335833,13409706116029,13421823366825,13433944864185,13446072730229,13458204336335,13470343449341,13482486824047,13494635283321,13506789816961,13518950016023,13531116736447,13543286630681,13555463267855,13567644820083,13579832646821,13592025780313,13604223669095,13616427995203,13628637321541,13640852094937,13653072091479,13665297256713,13677528917087,13689766195449,13702007829897,13714255377771,13726507653857,13738767313827,13751030763747,13763300541847,13775575383463,13787856426561,13800141931943,13812432953215,13824730146149,13837031857599,13849340367297,13861652823379,13873972794291,13886296216765,13898626055083,13910961166217,13923301434765,13935647644521,13947999729935,13960357012901,13972718916875,13985086527675,13997460130869,14009839531085,14022223758473,14034613351391,14047008811425,14059409736433,14071815808881,14084227590455,14096644589791,14109067969233,14121496095015,14133929611963,14146368515957,14158813109309,14171263075309,14183718072639,14196179628007,14208645671553,14221118126155,14233595797953,14246078122119,14258566810093,14271059760219,14283559583171,14296064549791,14308574852301,14321090240929,14333611218137,14346138588973,14358669448749,14371208272175,14383751059259,14396300025239,14408853149827,14421412810211,14433978428375,14446547587551,14459124401171,14471705585585,14484292967815,14496884553347,14509482568411,14522085736829,14534693918595,14547308199695,14559928003573,14572553236441,14585184007895,14597820172007,14610462025549,14623108227205,14635761005069,14648419143615,14661083211947,14673751416475,14686425143683,14699105590597,14711790385667,14724481853915,14737177453073,14749880364785,14762587132337,14775299078509,14788017882973,14800740432595,14813470164995,14826204862599,14838945312383,14851690540721,14864441325739,14877197685469,14889959698775,14902727246305,14915499920787,14928278977137,14941061789093,14953851247251,14966646243863,14979445863307,14992252168091,15005062944227,15017880093211,15030701351655,15043529133889,15056362150875,15069200748943,15082045386147,15094894443789,15107749552833,15120609997405,15133475472581,15146346770249,15159223436155,15172105860337,15184993349417,15197887010899,15210785714961,15223689577903,15236599372147,15249513976763,15262435700771,15275360913381,15288293050267,15301229443295,15314172255471,15327120303503,15340072898865,15353032847827,15365996557785,15378967396817,15391941753633,15404922507543,15417908922543,15430900336619,15443897619807,15456900611455,15469908646853,15482921665249,15495941727319,15508965468135,15521995573019,15535030355141,15548072265427,15561119216811,15574170279257,15587227640379,15600291163835,15613358795255,15626432686721,15639512048269,15652596855593,15665686908087,15678782038539,15691883457533,15704989790289,15718102122911,15731219990971,15744343142107,15757471032665,15770605573609,15783744969619,15796889270723,15810040127115,15823195666585,15836358065431,15849524202219,15862695978895,15875873890073,15889056899163,15902246009269,15915439685683,15928640447503,15941844734897,15955055575093,15968271353607,15981492520231,15994719920107,16007952054737,16021190243287,16034433519401,16047681803261,16060936854211,16074197075041,16087461332463,16100732892925,16114009305365,16127291146189,16140577339289,16153870119273,16167167881317,16180472092111,16193781229517,16207095659921,16220415702899,16233740731151,16247071866853,16260407311293,16273750673303,16287097670253,16300450630843,16313808469671,16327171945067,16340541319405,16353915768287,16367296434653,16380681995213,16394073403755,16407469470967,16420872054217,16434279472803,16447692119253,16461111489611,16474535288757,16487964562697,16501399009125,16514839634507,16528285517145,16541736022341,16555192686617,16568655452519,16582124252609,16595596457097,16609075263883,16622559477469,16636048586713,16649544151921,16663044310991,16676550818273,16690061783813,16703578696163,16717101644061,16730628675899,16744162154597,16757701349381,16771246537223,16784795545209,16798350415901,16811912072027,16825477387753,16839049884267,16852626119371,16866209611605,16879797570593,16893390607709,16906990295617,16920593661127,16934204456855,16947819691387,16961441504303,16975066792825,16988699060739,17002335904925,17015978804139,17029627283225,17043280590735,17056940255807,17070604754765,17084275038323,17097950823907,17111631839663,17125318340241,17139010486083,17152708006441,17166411290789,17180119120969,17193833303495,17207551802109,17221277899715,17235007750459,17248743955137,17262485310955,17276231156455,17289983710939,17303741001507,17317504983507,17331273255121,17345048565913,17358826854887,17372612662419,17386402373913,17400198427933,17414000654713,17427807083299,17441620060469,17455436629617,17469260731367,17483089553817,17496923079987,17510763454691,17524608918679,17538459923863,17552315315283,17566177597733,17580044720877,17593916613307,17607794896155,17621679000779,17635568337573,17649462258277,17663361632905,17677267564555,17691178276939,17705094802375,17719017133619,17732944131283,17746876909747,17760814330661,17774758668081,17788707600625,17802662811601,17816622490237,17830588499103,17844559305743,17858535506397,17872518579237,17886505276725,17900498808151,17914496548543,17928501051439,17942509985883,17956524981227,17970545115893,17984570784511,17998602288015,18012638963671,18026681764671,18040728683751,18054782199595,18068840701815,18082904816079,18096974723103,18111049397445,18125129930089,18139216126263,18153307168741,18167404493041,18181506488427,18195614060065,18209727806553,18223846534151,18237970760173,18252100826909,18266235389393,18280376515301,18294522935335,18308673992889,18322831880685,18336994178715,18351161317283,18365335329587,18379514185365,18393699081145,18407889447587,18422084614135,18436285675367,18450491493921,18464703631291,18478919760133,18493143989755,18507371319763,18521605636131,18535844238423,18550088779059,18564340149423,18578594465055,18592855818367,18607122169023,18621394905525,18635671875161,18649955132911,18664242971655,18678536958939,18692836492717,18707141746137,18721452140987,18735766907099,18750088447901,18764415754231,18778746945715,18793085033737,18807428752807,18821777852197,18836131420991,18850489696265,18864855459075,18879225910101,18893602029239,18907982689235,18922370461333,18936762192907,18951160730283,18965564481353,18979972320273,18994387536597,19008806431413,19023232938857,19037662861383,19052098365785,19066540184041,19080987133849,19095439776297,19109897320623,19124362255907,19138830666745,19153304478935,19167784535891,19182269685127,19196761316071,19211257003359,19225759487411,19240266196583,19254779085365,19269297837955,19283820556357,19298350219927,19312884771447,19327425370905,19341970662189,19356521025475,19371078630145,19385639913407,19400207924455,19414780347477,19429358862003,19443942854019,19458531742677,19473126557653,19487725930527,19502333458835,19516944318489,19531560946877,19546182711183,19560811079617,19575443800777,19590081865537,19604726512345,19619375464253,19634031466921,19648690535817,19663357500721,19678028216245,19692705090487,19707387762673,19722075461059,19736769319175,19751467817271,19766172754869,19780881791731,19795596623031,19810317218537,19825044302777,19839775781817,19854512311173,19869254060209,19884002771849,19898755620751,19913515219011,19928279952837,19943050786465,19957824978039,19972605025303,19987392127567,20002183260105,20016981262663,20031783365493,20046592499381,20061405371953,20076224923433,20091050044641,20105879223029,20120715063713,20135555963947,20150403175015,20165254584881,20180111755353,20194975092497,20209842906011,20224716778249,20239595864063,20254481847375,20269371465885,20284267197515,20299168160869,20314074935785,20328987457873,20343904791311,20358828532811,20373756760465,20388690488131,20403630104013,20418575199365,20433525315625,20448481519631,20463442323107,20478409678581,20493382136443,20508359842885,20523343032469,20538331942899,20553326453877,20568325917501,20583331082801,20598341349541,20613357664375,20628378875091,20643406252949,20658438962617,20673477499423,20688519927499,20703569287071,20718623949245,20733682799713,20748748888911,20763819399443,20778896678397,20793977844383,20809064727399,20824157450241,20839255178237,20854359514489,20869468590827,20884583149465,20899702699899,20914829199739,20929959763653,20945095625851,20960238149719,20975385228879,20990539185857,21005696804291,21020860225521,21036029929839,21051204110905,21066385223853,21081570807809,21096762114707,21111958495463,21127160271769,21142368404191,21157580641639,21172799322451,21188023972015,21203253838289,21218488502903,21233728280611,21248975459083,21264225737071,21279482611111,21294744634071,21310013632633,21325286772925,21340564657367,21355849163341,21371138121089,21386434161119,21401734273435,21417041398463,21432351828611,21447668754841,21462991228589,21478318975057,21493653425319,21508992582719,21524336764629,21539686363047,21555041848541,21570402449715,21585768980783,21601140521813,21616517653725,21631899909187,21647288262251,21662682093069,21678081384205,21693484855271,21708896489181,21724310822409,21739732973967,21755158551641,21770590282069,21786028703057,21801470287743,21816919691389,21832372543235,21847833276777,21863297261371,21878767366609,21894242564247,21909723803351,21925211433183,21940703142181,21956201220879,21971703029997,21987212432045,22002725986125,22018244376537,22033770021231,22049300688103,22064837277521,22080378056791,22095925364783,22111477669911,22127035089227,22142598726419,22158167004553,22173741880917,22189320915671,22204905876431,22220496519113,22236091591469,22251694307093,22267302153575,22282913577697,22298531808385,22314154566503,22329784353653,22345418041107,22361057541195,22376703285029,22392355213243,22408010637245,22423671748903,22439339432203,22455011350801,22470690961711,22486373033767,22502063318347,22517757432333,22533457906437,22549162729593,22564873392219,22580590312701,22596312120911,22612040308853,22627772063725,22643510380147,22659254111603,22675004147133,22690758744545,22706518648863,22722285036843,22738055729053,22753832046221,22769613903657,22785401837013,22801195209851,22816993353643,22832797516257,22848606884441,22864422169291,22880242518517,22896067504793,22911899704169,22927736656869,22943579009625,22959426393861,22975279585567,22991138791689,23007001915051,23022871782877,23038746646127,23054627774825,23070513751803,23086404735409,23102301824265,23118204019923,23134113325353,23150026278713,23165945472433,23181868787607,23197798552069,23213734650935,23229674245329,23245621090683,23261572409135,23277530683841,23293492673325,23309460639661,23325434656083,23341413446381,23357398047303,23373388474847,23389383671205,23405384388585,23421390962683,23437402822983,23453419736891,23469442570943,23485471776255,23501505362907,23517544280165,23533588474577,23549639878207,23565694511975,23581756255211,23597822742433,23613895638239,23629972212885,23646054801519,23662144195451,23678236762219,23694337274811,23710441696415,23726553039537,23742669092611,23758789532241,23774915920101,23791048186231,23807186199347,23823329241899,23839478663481,23855632149281,23871791409415,23887956665011,23904127095681,23920304139411,23936484942809,23952672670755,23968865316695,23985062368163,24001265684481,24017474748769,24033689098089,24049908830507,24066134344389,24082364762177,24098601098025,24114843092279,24131089019657,24147342671191,24163600837659,24179864619241,24196133456895,24212407588741,24228687909487,24244972637801,24261264343945,24277560583591,24293863017109,24310169406967,24326482594935,24342801203035,24359123792161,24375454578667,24391788662601,24408129128385,24424473273603,24440825243693,24457181757791,24473543369743,24489911360557,24506284649591,24522663512357,24539046559675,24555436980301,24571830785279,24588231570141,24604637543663,24621049007045,24637466096029,24653887282681,24670315254737,24686748982785,24703186431635,24719631501297,24736081176237,24752536782345,24768997159427,24785461738217,24801934081941,24818410790727,24834893471599,24851381521383,24867875604971,24884373769153,24900877656189,24917388271107,24933902394829,24950423347589,24966949566979,24983482169037,25000018891803,25016560741371,25033109597541,25049662564949,25066222080895,25082786400483,25099357165519,25115931673783,25132512886283,25149098782885,25165690522883,25182288711455,25198890736605,25215499980045,25232112956717,25248732541177,25265356655359,25281987099553,25298622201179,25315264099935,25331910555155,25348562738637,25365220156893,25381882043507,25398551191169,25415225569409,25431904786031,25448590026253,25465280830295,25481975914107,25498677214149,25515382932235,25532096145459,25548813879021,25565537343637,25582264806197,25598998815901,25615738762889,25632483760401,25649235524997,25665990212393,25682753352879,25699518910955,25716291510311,25733069283241,25749851818641,25766641995641,25783436133129,25800235793763,25817040282029,25833851284623,25850668330813,25867489229753,25884316132121,25901149478677,25917987899987,25934830734741,25951679193021,25968534112625,25985393365109,26002259314485,26019130277007,26036006628805,26052888426747,26069775217465,26086669240281,26103566440233,26120470706739,26137379860611,26154295164551,26171214409971,26188140066155,26205072058929,26222007449645,26238949627037,26255896955315,26272850907877,26289808516973,26306772117123,26323742145403,26340716521907,26357697229547,26374682851179,26391674723013,26408670361517,26425673095861,26442680664665,26459693812545,26476712123661,26493736062317,26510766728677,26527801241473,26544841662245,26561888304197,26578938895741,26595996637723,26613058344181,26630126645645,26647200327371,26664278081083,26681362689057,26698451261775,26715547939331,26732647912009,26749755319147,26766866605159,26783983545561,26801106050243,26818232616955,26835367635777,26852506071517,26869651290353,26886800207787,26903955895709,26921116681241,26938282660171,26955455460437,26972631833335,26989815285959,27007003273985,27024196965955,27041396534251,27058600660673,27075811103447,27093027412811,27110247901247,27127474180009,27144706121151,27161944101407,27179186199705,27196434430011,27213688888131,27230949680447,27248213152845,27265483346761,27282758835983,27300039275853,27317326920603,27334619197721,27351917207997,27369219481791,27386528519155,27403843081909,27421162061283,27438487853447,27455818337003,27473154181035,27490494659023,27507841522853,27525194633899,27542551435099,27559915654529,27577283835151,27594659531567,27612037646529,27629423674853,27646813669339,27664210295593,27681612697343,27699018490731,27716433355689,27733848940757,27751273081733,27768701884925,27786136086641,27803576299501,27821021512643,27838472989537,27855929387437,27873390059469,27890858083285,27908331172239,27925808820611,27943292610921,27960781444679,27978276545435,27995776229887,28013281815215,28030792484753,28048310037173,28065831884083,28083359371843,28100892444711,28118430492529,28135974746529,28153522974531,28171078644819,28188638900095,28206204365735,28223775401425,28241352629951,28258934555373,28276521328197,28294115523773,28311713726519,28329318158207,28346926555853,28364542455437,28382163769287,28399788943811,28417419857699,28435056822327,28452700099447,28470346825141,28488000849625,28505658195195,28523323246833,28540993315769,28558668815931,28576350143067,28594035148051,28611726788911,28629423918445,28647125923997,28664833615799,28682548545857,28700267160145,28717991711589,28735719995345,28753456785485,28771197182697,28788943580771,28806694706445,28824453021905,28842215308719,28859983067871,28877757713735,28895535414967,28913321539077,28931110478863,28948907158883,28966707005173,28984513531523,29002326191649,29020142547951,29037965808279,29055794994965,29073629838997,29091468445629,29109312345893,29127162664673,29145018424255,29162880039167,29180746524501,29198618514941,29216496531507,29234379357103,29252267757503,29270161728775,29288061497757,29305966728715,29323877195625,29341792469961,29359713741967,29377641047637,29395572619887,29413511739347,29431453913371,29449403837697,29467358186007,29485316949361,29503282519671,29521252320963,29539229276023,29557210639447,29575197748861,29593189815997,29611188333607,29629191898473,29647199758625,29665214607431,29683234261681,29701260598903,29719289515565,29737327393103,29755369456471,29773416137449,29791469624303,29809526903939,29827591509839,29845659751159,29863734871435,29881814656475,29899898940211,29917990725171,29936087920585,29954190145967,29972296511189,29990409460861,30008528311961,30026651139387,30044780867839,30062915931907,30081056919963,30099202238755,30117352022697,30135509760623,30153671617017,30171839831099,30190011948333,30208191862717,30226375253111,30244564649485,30262760525855,30280959433805,30299165807397,30317377236663,30335594525235,30353816317935,30372043555783,30390277346113};
int phi(int n) {
if (n == 1) return 0;
int res = n;
for (int 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 = 3000;
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(); }