#include <bits/stdc++.h>
#define rep(i,a,b) for (int i = (a); i < (b); ++i)
#define sz(x) (int)(x.size())
#define all(x) begin(x), end(x)
using namespace std;
typedef long long ll;
const int maxn = 10000007;
ll p[maxn], cntp, buck[maxn] = {664134,-58106,-18776,-11457,-8315,-6499,-5032,-4631,-3746,-3071,-2647,-3515,-1800,-2527,-1815,-2135,-1437,-1323,-2214,-1624,-775,-1775,-881,-1062,-1197,-1232,-1018,-839,-1091,-932,-466,-1511,-416,-1139,-209,-1159,-645,-149,-1131,-721,-729,-621,-195,-1066,-22,-973,-340,-464,-762,-445,-1114,50,-424,-328,-708,-181,-658,-247,-520,-210,-418,-797,-103,-620,-276,-170,-626,-301,-268,-396,-210,-831,-21,-305,-623,-156,-278,-263,280,-851,82,-693,-413,104,-450,-682,174,-575,-422,-248,539,-316,-1176,141,56,-202,-363,-700,347,-304,-376,-111,-341,-103,-756,69,226,-788,508,-471,-249,-583,-367,-305,-317,597,-89,-439,-721,255,-408,230,-1005,412,-38,-365,452,-1011,-46,-476,819,-1107,-99,326,-184,-42,-523,-529,64,198,-749,387,-362,-440,439,-469,-385,611,-551,238,-664,-168,294,-922,253,-33,-805,610,-364,-186,-82,-606,580,16,-832,-361,432,-71,113,-896,774,-562,-256,-452,256,67,-417,-52,-101,498,-834,-309,-3,134,-495,147,-263,31,-236,239,-502,-151,-100,39,8,31,-488,241,-202,-555,966,-549,-862,507,-186,-602,325,-177,38,-312,529,-252,-1073,-138,971,-497,-154,295,-819,212,-335,147,1,-226,23,-116,479,-342,-343,-23,-677,175,68,-79,-489,257,-51,-224,73,-240,-336,226,99,-135,-654,465,-321,330,-443,-278,264,60,-179,62,-167,-38,-46,-256,-142,52,-816,545,-312,-60,-251,336,-343,212,-110,-112,-74,-33,-950,670,-528,363,-81,252,-411,-224,390,-345,180,-730,339,34,35,-387,-90,-195,340,-593,496,-390,175,-721,565,-559,382,-697,88,397,-678,781,-411,-10,178,-202,-359,-374,-177,617,32,-756,491,-99,82,-569,138,-141,467,-965,361,-75,-161,615,-1363,678,32,-469,397,225,-491,-55,-180,-482,532,-10,-102,-309,158,-95,551,-1097,602,-334,432,-661,108,-60,347,-431,-67,1,-135,399,-663,-322,356,-418,278,-177,512,-551,534,-844,322,158,-785,229,-103,424,27,-279,-286,-177,295,-396,-28,-17,185,114,-507,56,-645,474,342,-486,193,-487,558,-998,426,426,-200,-356,242,-574,263,107,-315,-317,412,-256,53,322,-433,-428,282,40,96,218,-166,-400,-122,143,-623,57,543,-348,708,-696,-124,-200,467,-651,189,740,-787,-48,-689,1105,-362,384,-907,727,-538,389,-770,-109,431,155,-415,-329,-33,467,-580,-3,93,693,-762,268,-166,230,-728,347,407,-940,223,411,-388,-271,544,-870,822,-594,-10,417,83,-224,-762,861,-736,290,66,264,-1012,-14,536,-273,28,338,-817,515,-446,228,-368,601,-123,-218,-59,-472,490,-76,-213,312,-693,572,-656,-246,889,298,-563,-423,-373,559,-516,764,-343,-486,558,27,-171,-574,539,-14,-637,600,-424,234,37,-412,141,-203,470,-569,274,-602,1042,-590,-665,563,-304,-196,481,261,-816,218,-324,189,-255,795,-827,-74,562,171,-758,421,-583,252,-47,-235,23,307,-556,854,-576,264,23,-352,-69,374,-249,-344,327,-543,761,-224,-359,-277,255,306,-894,509,42,-447,221,-64,-340,14,326,-124,-202,440,-523,29,249,205,-1103,459,574,-903,487,-83,-26,-110,-123,483,45,-532,10,-434,177,88,-522,763,182,-626,194,241,-808,336,1097,-1207,291,-563,337,218,-477,733,-812,-74,-223,737,-1126,931,-703,1038,-318,-102,-511,125,-298,61,87,-513,917,-382,-217,-306,496,-640,668,-859,888,-777,204,386,-337,386,-108,502,-647,211,-783,-6,515,51,-226,611,-1044,325,39,-12,-384,278,-407,469,44,-504,304,-995,1329,-1069,770,42,-513,628,-683,-97,-138,338,224,-566,-130,278,-612,631,-633,1114,-387,-407,-52,91,-162,-165,555,-280,-221,582,-915,666,155,-793,784,-100,-485,169,-104,-2,-443,-96,1007,-673,-534,405,107,-483,267,-201,344,-385,469,-659,542,-302,753,-855,-370,268,231,-20,353,-56,-493,-435,690,-1234,1032,432,-79,-31,-909,394,-11,102,-291,-325,377,112,-38,-133,-150,-136,-94,326,56,-884,586,-378,16,401,419,-655,-273,367,125,-166,-272,40,-164,687,-499,28,-325,333,483,-542,-30,-387,457,-192,665,-411,-139,-626,596,-651,430,-68,882,-1484,576,46,-67,98,-201,441,-341,-176,794,-902,-85,-154,217,45,-95,648,-747,181,-351,206,-317,-150,688,-667,550,-872,675,318,166,-401,-415,327,-375,323,-109,428,-519,-415,636,-800,99,639,-287,27,346,-890,365,-370,451,-237,333,-245,-500,-100,712,-649,794,-559,94,61,-86,-9,220,-161,140,-806,726,-204,175,-872,636,-191,50,-278,-137,201,-177,911,-548,-114,-147,216,-622,297,-242,277,437,-308,-120,-47,114,63,-29,-165,-317,93,68,25,-355,-34,645,-337,190,-233,-481,864,-636,209,58,317,-226,-510,-69,212,15,-31,100,165,-862,1084,-1153,903,-761,189,-480,1106,-1396,606,1150,-1137,622,-160,-416,194,683,-748,314,-536,-220,527,-134,-397,10,19,-209,288,100,381,-732,746,-829,705,-543,-352,574,-443,-132,435,-297,352,123,-344,-641,612,358,-743,632,-245,-69,54,435,-994,-29,923,-68,-459,227,-100,206,-441,-302,422,-273,-315,610,-310,-70,134,224,-585,60,511,-791,488,-315,500,-355,235,-733,389,385,-306,-259,300,174,-913,791,-130,225,-56,-835,344,-75,360,-928,1085,-375,63,-215,-200,191,-76,240,-511,401,-160,-289,378,-367,578,-420,129,-509,370,-480,861,226,-443,-262,312,-310,-639,1072,-950,561,-649,876,-225,-627,-331,1179,-207,33,-813,446,12,-521,893,-915,434,-126,-796,457,1071,-241,-323,407,-517,-148,-83,474,-220,-75,-515,321,-424,1307,-579,-804,638,-289,-150,851,-595,181,-186,284,-46,117,-522,127,-696,349,-237,47,-41,1120,-864,638,-1127,668,8,-445,-326,771,-453,174,620,-788,314,-401,-4,203,75,-787,932,120,-313,24,-133,-72,180,322,-782,237,-50,229,81,-1078,348,-203,673,-227,-54,475,-677,-344,698,274,-939,888,-637,-391,427,709,-889,718,-579,-538,671,-260,257,57,14,-879,1354,-469,161,-426,67,-81,338,102,-601,792,-418,122,-109,-747,-25,487,-383,242,426,-50,-396,98,813,-1153,-296,354,-81,477,-613,106,-240,712,-239,-531,250,-74,375,-439,124,-59,810,-587,-359,38,25,-40,-121,-33,-285,643,-26,-195,210,-569,486,-493,319,359,95,-780,303,-160,794,-1002,67,787,-456,155,40,-760,192,-196,40,489,-210,203,-11,283,-934,249,334,-575,510,24,-1042,1169,-410,-108,-111,-301,758,-293,18,-541,1331,-937,143,412,-614,181,366,-644,309,-485,450,-401,606,-385,86,5,-395,-434,570,-158,-325,563,-396,379,-383,6,455,-151,98,-237,4,-723,817,150,78,211,-1064,635,-814,948,-201,-538,207,457,-43,-371,169,-82,127,-338,199,243,-308,-263,179,53,187,-777,353,23,-24,557,-404,-544,529,-388,323,-383,561,-1199,1120,20,-380,-125,188,340,-371,472,-637,201,16,-85,27,-125,90,-95,-57,-273,333,92,185,-788,690,-424,50,287,-461,721,-143,-626,-16,474,-305,361,-581,63,239,124,-420,107,-289,252,144,-96,-63,-529,1163,-658,95,301,-653,645,-278,39,-328,313,-474,-321,823,-1050,1245,138,-1031,553,40,-326,299,-219,84,-384,-266,591,-126,-155,-240,246,-417,645,-314,242,3,-552,596,39,-334,349,-79,-602,28,401,-495,-256,1140,-730,172,-320,354,-868,443,370,244,19,-255,-305,364,399,-1030,441,26,61,-280,455,-730,401,-52,183,5,87,-35,-499,751,-598,-49,90,-677,6,1125,-343,-99,-412,533,-245,-311,293,478,-252,-335,9,-250,300,-30,-75,-242,-19,345,464,-180,-962,720,-511,547,166,-410,442,-1122,517,-215,473,-487,860,-998,183,436,-151,344,-521,236,-258,469,-754,243,479,-384,-161,187,-483,129,81,-470,640,-132,-61,361,-6,105,-93,-1005,150,702,-295,359,-511,-82,308,0,373,-432,-261,258,673,-766,-267,768,47,-305,-566,483,-435,-250,1018,-379,-690,310,142,304,-796,298,423,-512,-704,1198,-454,131,152,-189,-390,497,564,-777,69,-268,-8,452,-527,203,426,-532,-42,-227,1124,-1410,880,616,-850,-10,703,-595,-183,-650,786,-375,697,-683,792,-796,97,503,-598,356,-590,514,-127,-574,-35,550,546,-1230,643,237,-255,-221,250,354,-698,140,-383,457,343,-862,408,-324,600,-320,142,-50,107,286,-1329,850,-263,170,9,282,93,-141,-514,-292,605,154,-11,511,-922,-225,-154,559,420,-572,371,-469,-116,-101,409,265,-557,91,185,-495,470,456,-744,386,-925,949,-606,667,-244,-828,389,217,96,187,-622,658,13,-396,98,-360,-30,944,-1089,240,336,-62,52,85,-395,688,-1172,417,329,-213,209,-413,699,-622,358,-416,247,27,-297,297,-785,859,-487,885,-624,-42,368,-791,717,-527,108,-197,141,539,-623,43,270,-162,-52,141,40,-366,223,20,-246,-312,623,-385,112,-73,188,-93,-95,726,-744,-730,390,419,496,-1271,280,339,-154,277,135,-82,104,268,-267,-958,513,-14,117,-366,597,-495,-262,980,-364,69,-22,-279,-357,484,-464,268,-185,481,-1045,801,53,-65,50,-586,365,4,788,-731,109,397,-936,546,-269,130,204,-58,-185,137,-394,199,-333,-235,628,8,-428,365,366,-76,-743,881,-414,-170,-593,611,-204,231,-40,-517,647,-312,269,-366,740,-233,-522,140,518,-715,460,318,-602,-254,190,5,-31,157,-90,-15,150,-277,-430,1079,-1090,1049,-395,-175,70,-537,611,-545,-273,209,148,280,596,-834,-99,133,159,177,-635,621,3,43,-686,197,330,-354,-223,116,958,-1137,175,699,-596,636,-531,-373,217,102,-133,276,-205,454,-472,443,-213,-441,45,-237,-179,695,-272,266,-165,-52,224,-173,-492,409,635,-548,-66,-77,-370,467,196,-633,1110,-1316,562,361,20,-928,-396,834,178,158,-797,-9,102,648,-524,468,177,-911,593,-545,350,511,-949,500,430,-13,-253,-340,-590,713,-72,-44,-506,900,152,-179,-963,572,78,-208,385,-192,370,-710,838,-488,-169,-357,901,-457,-11,-448,469,-130,280,-258,-105,1032,-1177,-36,-334,979,-218,-668,-322,1149,-446,-198,215,441,-1060,710,407,-534,-551,346,534,-538,79,203,-346,-119,210,-431,514,-536,679,-654,76,333,495,-651,-25,516,-341,273,-355,283,-318,122,-41,7,58,-15,-633,-40,515,35,-257,-233,125,783,-366,-241,203,-28,35,-902,834,-396,381,255,253,-1000,-186,1018,-591,428,-697,159,-84,-156,49,826,-237,-449,208,95,-30,-143,91,-661,152,782,-553,605,-598,456,-576,416,131,-353,318,-751,628,-81,-193,-520,518,249,-393,-121,459,-432,270,-37,129,128,93,-348,407,-1079,548,-65,7,36,-17,125,-211,-155,438,282,-598,371,158,-264,-591,242,-68,196,83,-76,213,-337,-280,373,-237,692,-554,95,-317,225,-194,801,-1253,837,-223,-809,1187,-221,140,264,-999,444,422,-64,-938,263,545,-407,119,-127,335,-799,981,-741,463,29,-485,-361,260,659,116,-165,-658,341,385,-385,-143,160,-238,13,301,185,-471,80,130,-237,-475,225,445,-112,234,-355,265,-143,-599,1411,-983,-349,319,185,-324,350,130,-516,245,-603,691,-233,17,-349,410,208,70,-490,336,-239,109,614,-729,-559,561,-415,1058,-492,598,-952,429,-137,-524,1041,-412,-406,21,-57,750,-479,320,-642,-39,398,763,-1838,678,391,-594,18,-336,553,-172,93,341,-410,1272,-1101,92,342,-1179,844,-355,-78,528,-364,-178,590,159,-604,252,163,-643,746,-218,-156,73,-27,-302,-201,137,235,892,-1313,267,293,-859,1469,-920,166,229,-99,-676,577,-488,280,79,237,-490,244,-800,772,-685,589,-521,623,44,-366,124,270,-93,546,-870,776,-758,-21,257,177,-4,-198,-195,55,246,-158,587,-584,-602,643,-261,667,-726,-180,1411,-859,-257,172,-39,-337,144,73,-11,-620,787,-193,277,-39,-482,199,-338,-47,112,410,-254,-334,653,-95,-123,234,166,-1139,187,494,427,-615,-374,705,-190,-58,269,-238,-339,128,414,-13,-882,933,-111,-411,210,-193,390,-634,373,207,-736,566,-217,-370,266,685,345,-225,-1515,653,447,-220,-271,479,-312,294,-17,-512,876,-1137,481,-65,51,153,-225,822,-883,-413,627,-36,184,-44,128,13,-523,441,41,-322,-28,721,-994,661,-523,429,-525,142,249,-180,491,-406,374,-613,307,-532,-104,822,-543,-233,407,261,-343,-715,585,280,-428,-450,654,54,-421,724,-15,-454,784,-631,-447,157,475,-132,37,-866,1229,-1369,1349,-372,-716,646,479,-256,-187,-164,208,-195,199,-579,32,624,-357,72,-215,-254,257,674,-234,-385,324,-726,-183,-159,1205,-692,80,520,-487,468,-1295,909,-11,-178,391,-140,-180,-107,505,-1276,1186,-72,-21,-296,-960,1166,-49,-321,-125,53,7,-121,567,-59,349,-61,-227,-484,-216,538,134,-349,-216,-16,183,35,-364,681,-272,739,-809,-102,212,-136,-152,650,-998,95,393,-314,-72,1373,-744,-772,907,99,-921,618,-97,0,2,-247,-190,172,242,-83,-47,-372,305,255,207,-414,435,-473,-355,689,-382,361,183,-773,376,-479,264,-595,996,-433,-436,727,-408,-38,304,-482,1171,-348,-318,-242,-55,262,-654,896,-704,38,-39,285,362,-329,-290,431,-1198,1151,-285,71,-64,-198,373,-254,-226,804,-429,16,-468,648,-281,-382,512,92,-603,959,-905,676,22,-725,806,-410,-287,-91,258,-569,66,1092,-1099,664,186,-551,-33,325,-933,765,-577,834,99,-448,608,-595,-24,-11,-349,831,-6,-449,416,-844,142,211,156,212,272,-1156,254,478,-112,45,-677,950,-396,41,-12,-579,484,-79,144,-194,465,-332,493,-648,-34,-109,-135,1026,-623,-221,183,-118,139,-367,671,7,-435,145,-116,263,-314,407,-450,224,-359,314,47,-274,229,18,-199,362,-470,-100,553,-879,413,393,-774,804,-209,-51,-164,-63,453,83,-386,115,-392,192,26,-104,272,-678,385,920,-789,-354,531,-236,6,-331,210,285,-605,716,-121,41,-1165,1269,-842,795,-506,-144,-31,-110,156,192,-6,362,159,-783,513,4,-236,283,-255,144,-542,223,134,-179,-90,235,399,-350,-198,519,-317,-157,750,-796,-394,260,86,321,-249,-201,-110,970,-536,-204,-267,248,665,-428,24,-266,-165,891,-803,549,-626,9,-197,88,43,290,-486,105,962,-852,441,-347,-182,739,-282,407,-845,-8,-327,557,6,95,-361,865,-323,-528,-139,902,-1118,787,-487,-235,489,568,-390,-846,733,-484,673,-578,-165,466,198,-106,-93,255,-945,558,-85,-221,-230,352,-66,-276,266,75,43,-33,531,-1249,1295,-313,47,-385,163,-57,-68,-162,213,217,72,-115,-48,-225,374,-46,-520,-267,50,927,-148,-246,-250,107,238,-396,366,-615,90,227,218,-346,133,-450,164,928,-1051,-142,793,-395,-305,478,-201,188,-103,439,-451,266,-185,-554,255,274,-381,610,248,-243,-513,687,-631,508,-615,342,-54,372,-738,221,-276,485,-433,345,518,-241,36,-62,-352,-132,205,-501,287,-341,850,-358,577,-383,-462,125,187,161,-273,417,-688,-249,243,130,297,-104,-253,64,565,-455,109,-208,121,26,-283,-8,181,24,79,450,-551,-480,1213,-1538,914,-109,-588,345,557,-342,-208,577,-538,-335,227,120,64,121,-524,92,-85,490,-298,-106,616,-511,473,-127,-990,1135,-711,939,-1196,527,-64,782,-539,-277,-11,-301,619,-561,200,604,-516,-14,45,-169,271,32,-168,324,-24,-455,-195,-73,502,-99,-261,199,-512,78,220,385,-100,135,-350,349,-228,-14,-174,26,576,-358,707,-1056,482,-283,-203,842,-437,-2,-709,778,-78,-340,233,-85,202,-602,291,224,-114,-733,853,-274,250,-858,1114,-972,891,-133,-191,-80,-159,-483,976,-113,-538,61,369,7,62,-230,306,-592,731,16,-414,503,-368,-428,276,292,-360,-378,518,-8,-56,-312,312,-179,398,-1038,1009,-219,-53,-210,-60,88,177,-384,280,-96,95,-396,-30,626,-437,125,392,-195,126,-32,-669,628,-334,731,-765,346,-177,315,-175,-576,530,-466,583,294,-495,490,-839,338,-123,297,-311,-269,873,-702,86,-157,-146,746,-23,-433,-32,30,-805,341,855,-464,139,987,-1280,-61,16,776,-875,-192,72,-425,869,-4,-223,681,-663,24,110,-345,781,-451,-665,1002,135,-1137,454,257,-739,403,248,945,-1000,260,-664,808,377,-936,395,-241,-28,-512,854,20,-592,528,-177,-292,-421,610,571,-837,53,-293,415,758,-405,-98,-300,12,-34,-207,52,-159,459,-371,-56,697,-452,-192,-395,1150,-426,-23,-344,167,-103,729,-468,-313,80,96,158,-289,167,-509,703,-112,-392,-26,600,-358,-326,710,-301,366,-497,476,-441,-245,53,533,-613,248,-234,454,-246,256,672,-1078,-327,569,121,-493,330,2,-56,239,-394,131,60,-326,440,-101,-195,-230,156,-220,40,77,200,-244,678,-213,106,-797,771,-249,194,237,-708,49,289,-91,-65,-207,218,211,-443,-534,666,17,-97,-102,184,371,-477,561,20,-542,-190,303,361,-816,650,-819,416,230,72,-219,-51,-301,610,-466,313,-462,20,50,-406,189,838,-136,-167,-164,118,-120,251,814,-1212,402,170,-539,-54,783,-1172,741,-395,449,130,-98,-1054,1191,-173,-935,291,571,79,578,-626,-499,478,-291,165,306,-691,67,184,-582,545,446,-245,-383,363,-264,234,-554,563,-702,738,-337,326,-392,445,210,-966,643,-772,-108,701,-20,28,-339,226,-119,-303,644,-383,203,101,459,-433,-268,126,139,-425,57,198,271,-155,-375,-488,1044,-239,-271,-659,803,395,-655,-88,906,-730,80,45,197,-367,-18,30,82,311,-837,772,38,-19,-1235,1055,-190,108,23,-392,-89,471,-401,880,-450,311,-112,-205,-491,-38,275,406,-210,239,275,-338,-283,82,-102,-29,319,-289,-346,-188,935,-192,-566,152,-181,772,-260,-4,-269,143,-215,375,24,-133,358,-475,121,-372,-598,1004,371,-141,-952,1036,-354,-14,-315,51,641,-136,-571,-1,48,-574,1027,-839,928,177,-654,-98,254,100,159,-234,-853,982,-262,100,-271,48,-282,132,1012,-1077,300,508,-305,-768,518,-274,466,-483,323,-222,-136,986,-529,-391,-243,780,-607,180,352,-226,-376,276,56,38,-648,9,632,77,-58,-296,429,-775,939,-497,263,-87,395,5,-1175,702,152,-223,-614,1273,-270,-367,-536,468,-104,-168,-51,-96,295,-581,651,-4,269,-395,227,-437,835,-288,-140,64,-453,419,342,-189,-736,508,29,186,-613,235,-128,427,103,-308,-235,509,19,-1092,550,651,189,-846,-134,372,325,-302,-410,-333,950,193,-441,442,-1187,669,-20,-250,280,-200,173,-187,509,-589,509,75,-548,334,-755,214,936,-1190,778,246,-102,115,-222,-103,-161,-165,-450,501,629,-317,-320,14,-257,333,197,-154,-336,17,325,232,-380,710,-727,667,-973,120,590,-274,735,-698,-155,521,-473,203,-672,59,232,431,-325,195,45,-804,874,-515,153,681,-656,86,61,-358,209,259,-152,-439,91,556,-253,-15,-799,1231,-1186,1145,-1138,-5,670,181,-790,223,507,-396,119,-644,548,517,245,-966,349,126,-82,242,428,-588,-303,1,123,-99,145,-45,-84,217,511,-347,-240,26,-36,355,-362,-127,-275,-206,787,-221,182,-860,474,-168,378,96,-394,137,572,-918,540,-100,30,-996,820,118,241,-547,229,325,101,-97,-599,388,-875,501,111,470,-189,-350,53,392,-769,354,475,-96,-94,197,-854,309,147,2,568,-1083,196,488,-220,9,306,-182,274,-775,215,508,-1238,1642,-730,-35,79,191,-290,-4,-15,217,-20,-431,558,-1336,816,456,-423,-21,-58,442,-12,-110,-452,576,-409,-3,-65,511,-750,598,-48,-38,354,-643,157,88,38,83,-784,1186,-769,252,372,-343,-69,-177,-494,820,-531,930,-1249,115,585,-151,450,-109,-201,-247,184,-535,1095,-957,161,223,99,-220,403,-640,187,80,16,539,-162,257,-414,-505,96,94,301,-309,456,-246,-70,-595,371,-204,233,279,409,4,-553,-299,459,-817,594,35,319,-644,449,-586,13,-378,446,360,-364,577,-613,236,56,-95,-347,707,-423,615,-459,-34,-379,388,-232,50,256,-201,673,-1255,1374,-632,-385,575,-46,-581,110,537,-295,0,35,-628,546,-713,620,260,-360,432,3,-583,51,105,669,-583,-310,796,-829,368,-15,-494,431,-286,191,-24,-348,162,193,441,9,-214,245,-276,-143,-99,433,651,-912,85,-15,-64,-100,189,54,-205,323,-693,245,135,-383,-385,98,437,419,-13,-161,-360,161,-393,732,-315,407,-551,318,132,-315,152,-682,1254,-865,32,271,-457,522,107,-728,784,-470,409,-121,-20,-538,810,-325,98,-380,-858,976,-248,-181,135,-33,-210,927,-1017,756,-311,630,-198,139,-120,144,-731,306,-471,39,959,-1120,891,-749,405,247,-325,502,-163,186,-374,-586,553,39,-535,823,-739,643,-94,-3,-540,-1,224,392,-550,-5,-15,-41,592,-4,-271,-310,289,77,-552,-52,630,-271,-786,824,-24,161,234,-308,-366,-600,1075,-274,-347,813,-582,-145,92,863,-482,-382,466,-93,-192,471,146,-186,-643,507,-918,998,-313,-363,265,133,-666,828,-90,-167,391,-266,-346,139,-198,-72,-25,273,235,-204,1131,-783,93,-755,965,-659,-99,-230,179,41,284,-852,661,-71,-397,649,-65,-303,303,-357,23,353,-111,-347,98,739,-431,588,-252,-1023,649,-527,334,-194,-152,164,-179,342,326,7,394,-708,31,-769,356,725,-285,-279,399,-121,-196,82,-683,245,178,-155,12,584,-127,-649,799,-804,974,-1065,522,-431,568,87,-78,284,-360,664,-339,-943,311,494,308,-348,-375,402,173,-938,759,-13,-33,10,-444,12,428,-217,109,-87,101,-188,652,-826,-65,227,447,-432,-10,308,20,358,-558,40,-522,657,173,-167,-352,36,-333,102,373,-220,-466,15,131,722,-415,238,327,-308,9,-102,257,373,-1584,1338,-394,-275,288,-1132,1728,-771,92,289,-273,-764,1381,-415,-1023,562,267,-44,-456,580,201,-112,-270,-492,525,-122,668,-933,-25,594,45,84,-557,13,280,-47,142,603,-1376,270,79,253,-436,696,-523,183,599,-983,149,109,111,-97,-211,-82,771,-834,674,-306,-61,1021,-874,-21,-371,346,472,69,-1295,890,-746,839,-412,-255,261,802,-658,31,204,-96,-153,-313,-29,-63,-60,194,-239,226,324,272,-137,-79,-600,252,-71,299,-315,-195,88,-197,64,309,-4,-539,1187,-970,468,407,-620,465,-797,1084,-855,746,-544,-511,1091,-978,408,-26,-1108,1057,-448,527,329,-264,23,-442,835,-700,122,449,-545,156,-20,-193,-37,207,-161,119,277,-339,691,-1397,876,-101,-294,-67,377,161,101,-79,254,-565,40,-9,-477,121,835,-244,-214,-189,537,-96,-408,263,-350,784,-549,-341,135,407,-697,790,-341,241,-164,70,-342,-42,441,-506,481,-174,-368,639,-117,-356,608,-410,-109,309,-313,-162,739,-333,-223,-421,982,-617,287,-381,363,38,-196,375,-465,34,148,-754,531,731,-764,26,-254,49,92,-156,382,-257,732,-454,39,46,-468,232,-287,215,-181,101,-518,1036,130,291,-500,-593,-111,217,39,356,-468,463,111,-477,353,156,-195,-430,347,116,-575,532,-136,-462,537,110,-730,-87,378,-225,785,-143,-695,414,-357,420,399,-545,-209,507,41,-333,193,86,-340,-245,1212,-1133,396,-699,889,-795,712,-152,-66,308,-212,-333,496,-917,613,160,-382,408,-390,-258,430,95,349,-340,237,-258,-706,836,319,-188,-409,-731,1041,-449,570,-1157,474,350,-568,680,191,-484,76,105,595,-785,-380,-93,654,-156,583,-787,518,459,-804,-193,477,-60,-490,346,-506,564,-646,1086,-1139,667,55,-259,-237,330,-245,63,311,-221,-61,364,-27,-465,-182,295,174,35,121,-729,613,485,-1176,840,-4,-1053,270,1027,-899,-354,681,-84,-170,187,412,-270,-365,179,452,175,-260,-693,34,491,-353,517,320,-804,287,-317,240,268,-87,-14,-464,23,560,-482,16,505,-563,99,-23,620,-19,-643,167,117,-797,397,294,-249,718,-209,-856,734,-55,-608,45,702,-81,-271,-200,201,-19,247,-708,330,-26,-483,812,-315,206,-838,814,-84,-366,238,363,-126,84,-136,-61,-171,-292,126,689,-322,-2,-574,886,-688,573,-344,-268,-132,338,529,-546,-191,311,-158,250,77,-466,256,576,-299,-607,590,154,-782,971,-499,1,-227,375,-264,508,-514,-716,1048,-902,811,192,-469,441,-424,44,-355,349,-314,217,188,-12,-767,278,248,5,-201,981,-882,387,-619,1045,-328,-332,74,105,-291,-96,163,-263,327,525,-238,-1020,717,71,-575,758,-208,-155,207,-286,-555,1039,-580,-259,-293,602,217,-183,-317,599,-540,554,-650,542,-243,80,103,246,-703,620,-121,-99,-198,-443,891,-353,228,-199,456,-3,-268,-94,116,-203,-59,-173,632,-454,-311,591,-902,825,212,-843,341,-457,609,-412,546,99,-414,445,-501,1175,-1281,397,-540,220,-191,393,201,-194,-345,75,-356,673,-176,798,-839,275,-52,-815,558,-278,640,186,-749,-79,659,-551,556,-127,85,-52,-850,519,419,-44,43,-409,36,235,-404,288,386,-330,-137,-73,152,-415,705,-502,-55,-333,347,-184,704,-416,-16,-327,282,-57,-129,99,280,310,-866,503,-182,10,-478,886,-376,-60,229,-399,253,185,-292,190,-184,136,-155,-244,-181,821,-1015,1136,-605,89,246,-314,300,-481,806,-143,-460,-27,218,133,-423,157,184,-77,-247,-145,72,587,-332,-162,-191,-14,-265,699,-115,-382,394,783,-391,-632,102,-214,314,149,194,-1234,974,-97,276,-186,-161,-34,555,-516,-275,413,196,-430,327,-47,-158,84,102,-528,362,-14,351,-183,-248,-233,454,-428,854,-819,-496,809,-419,392,-322,-29,-322,1075,-744,1039,-708,190,-460,146,251,153,154,-880,320,-206,-449,899,220,-648,-192,-45,-183,619,585,17,-1490,1393,-331,-1039,862,-492,116,41,-49,397,151,-35,21,-1002,681,-204,133,-22,108,795,-602,-276,556,-506,-575,477,-142,309,-363,510,-417,158,-329,224,-609,1049,-475,286,268,-573,-199,213,-73,410,-109,284,-531,-631,1433,-78,-533,-239,180,-172,347,-49,-39,169,-200,-316,1113,-779,-174,326,-272,712,-1695,1066,-543,465,-781,367,-97,1091,-1362,473,642,-1004,804,-314,272,-915,1086,-239,-241,-106,110,-366,1090,-980,306,949,-566,-24,-314,-62,794,-83,-622,-128,47,-76,510,-122,-573,-624,813,757,-912,686,-716,-90,781,-576,814,-429,-623,330,377,63,-399,-92,-19,-269,613,-48,-459,221,641,-282,-293,118,-325,199,241,-560,152,37,223,110,-647,476,-180,634,-501,-429,605,-95,-332,96,528,-895,306,-47,-157,294,141,501,-733,95,-290,471,-292,432,-626,546,502,-414,-272,-281,-25,-16,456,190,-654,259,-108,-615,1279,-763,365,99,-216,127,-179,-192,115,85,-19,-3,-208,582,-785,-449,966,-62,61,-341,-66,466,-654,702,-573,183,-420,360,-206,287,-199,287,18,794,-306,-412,-870,654,313,-325,111,9,-86,17,-572,829,281,27,-709,355,-94,135,-101,-354,118,79,205,-537,740,-708,759,-313,-521,8,620,-245,71,152,-106,-597,309,6,296,-391,291,19,-417,162,-687,623,494,-507,137,935,-672,109,-402,-129,52,118,412,-552,-393,-287,773,-396,946,-237,-1424,1295,-465,310,-289,497,-393,-339,273,298,-226,182,-477,628,-240,157,-1107,705,19,426,105,-620,584,-80,461,-657,-21,-258,304,353,-586,2,121,113,-920,1030,10,-141,285,75,-129,-174,279,-207,-76,42,-484,448,304,-355,-102,-344,68,208,-150,266,323,-41,-324,-222,306,-88,-356,779,-204,-599,147,491,-154,-590,442,-489,582,-911,1160,-65,-438,189,-330,39,-223,369,237,139,-433,-371,677,-593,508,43,458,-749,898,-1121,-103,796,-618,548,100,-509,300,71,-268,-105,91,136,-320,-266,325,10,488,-556,242,622,19,-522,19,-501,-93,514,201,272,-831,-212,592,-408,534,-333,65,-147,-189,259,667,-1003,310,92,-211,211,-439,514,108,-141,-512,330,-561,364,311,146,-527,471,-577,490,-315,443,254,-722,518,-502,802,-1384,1261,-226,-953,425,512,-750,241,-183,1444,-1662,673,-89,-133,816,-720,260,-762,745,-185,-392,976,-808,221,225,-54,-70,-489,102,-79,156,422,-739,399,-77,-83,-365,840,709,-1249,1276,-1208,-188,-91,224,406,-251,329,-289,-633,1191,-437,-162,-155,700,-485,-174,633,-1106,1364,-300,-371,-225,12,456,566,-948,432,-301,390,-342,371,-486,-468,434,132,-418,-506,437,206,149,-474,286,539,-699,1032,-1327,18,977,-70,-1132,590,847,-662,179,-146,-95,776,-989,191,153,-578,773,-212,521,-564,287,-442,618,-366,-122,9,126,-549,443,93,-184,454,-307,-554,48,809,-175,-59,-152,260,51,-547,785,-767,493,69,-665,686,-955,880,-605,382,-335,79,-221,378,-175,-337,596,-574,337,225,-457,390,-689,335,146,548,-726,570,-431,482,-224,-334,19,397,-385,-278,606,-80,-269,122,274,-229,4,486,-735,-278,766,-523,1111,-1245,394,152,492,-477,-672,398,59,-228,23,496,-62,-144,-121,186,-282,-4,300,-748,582,102,-491,579,-353,320,396,-491,-112,-481,802,-708,511,-504,547,-1119,735,807,-29,-1025,833,-246,66,131,-170,-446,471,73,-542,138,510,-823,116,112,692,-388,-291,61,-230,256,-252,354,628,-576,-468,-20,802,-635,639,-783,515,169,231,-610,99,-328,30,184,-177,167,518,-972,-59,902,-917,789,-162,220,-70,-595,643,-37,-412,793,-551,-475,729,-711,4,356,324,-199,121,-257,-349,431,-37,-560,136,23,395,-434,594,-989,383,660,-233,781,-784,-201,310,-313,514,-900,264,424,-155,-135,642,-603,163,78,-441,521,-88,-424,-149,-122,930,-647,-480,1217,-1254,1027,-599,-196,957,-485,322,-113,-437,257,28,612,-1057,-165,457,436,-655,778,-144,-878,25,487,28,-396,287,734,-476,-284,105,-194,565,109,-857,573,-527,552,-288,192,433,-561,-299,-19,806,-840,-124,629,-765,549,-850,-161,868,-512,1076,-87,-10,-422,555,-845,-92,719,-277,456,-1220,1632,-1415,573,-192,353,-602,899,-326,-205,184,-64,373,-244,270,-755,410,-515,251,167,-296,400,-710,236,399,-372,403,-709,702,-316,331,-151,-212,520,-797,-40,428,-266,351,-233,723,-913,158,523,-124,-133,-259,288,-749,566,182,91,-292,575,-677,-159,425,-126,217,-62,216,-419,519,-866,134,296,227,-279,-401,458,94,-430,307,-139,342,-323,-3,-173,243,315,-250,352,-558,-43,-31,726,-689,49,-263,429,-190,120,-134,42,-204,-342,182,235,-474,1134,-650,219,-820,598,422,-399,-3,486,-723,406,275,-519,385,23,-1003,995,320,-122,-348,248,-718,1193,-986,151,338,-522,180,-108,545,-223,-290,23,-394,446,-421,241,125,-22,199,-382,690,-672,182,75,141,206,-588,268,-254,353,713,-793,322,-1207,472,183,-442,1197,-411,-420,785,-801,605,-523,-61,563,-222,-487,375,28,-220,-466,955,-377,-272,724,-438,-248,247,86,103,-303,481,-69,-219,-221,-34,-534,818,-18,-308,494,-908,603,6,166,362,-1252,1024,-219,47,-239,-468,970,-226,-373,310,-31,-799,687,-511,486,-62,107,-167,-168,-3,644,-339,-595,770,-7,-543,748,-647,614,-844,39,340,358,-185,-540,68,1116,-1067,-341,257,101,913,-712,548,-715,477,-203,-162,154,395,-400,-182,494,-804,335,8,-682,585,517,-164,316,-454,212,-211,92,0,68,-728,338,267,149,-327,285,-376,-87,295,-5,415,-467,-182,-53,728,-195,-452,257,-751,781,-119,124,-532,564,98,-367,173,-293,-605,960,-270,89,62,51,461,-955,185,175,248,-406,122,-10,-398,596,92,-692,401,-133,-123,311,-41,-56,189,-674,532,-141,148,88,157,-1055,614,920,-695,-173,106,204,-630,886,-1028,1112,-1138,857,-531,525,67,-383,-617,563,-676,545,-181,724,-319,-447,820,-401,-327,719,-868,145,408,170,-744,307,502,-416,499,-868,159,402,-360,96,22,-142,581,49,-445,-319,-229,853,-81,-386,573,-888,256,156,239,16,-630,538,-457,-402,750,-153,-236,256,510,-330,202,-834,1118,-492,-570,333,201,79,-221,7,111,-278,-231,852,-134,-380,570,-1087,139,167,-249,1008,-146,-136,111,202,-534,-248,401,-537,77,870,-561,-225,198,-206,454,288,-238,-387,-32,-346,970,-1156,92,1007,-341,-128,-297,848,-551,-145,431,489,-687,-560,115,1029,-974,439,-21,-170,-173,528,54,-226,-729,296,-453,101,980,-567,208,212,170,-190,-64,26,259,-708,572,-142,65,-81,-258,148,469,-699,-56,89,404,-294,-185,453,-161,-35,-105,-722,454,579,-814,1004,-564,-213,379,-320,-49,621,-745,-161,212,151,267,-670,953,-102,303,-899,755,-751,586,10,-752,450,-218,287,672,-583,76,-254,-92,310,40,-404,202,-428,853,-1065,389,443,60,-767,707,-142,-100,-17,-279,-341,734,95,155,-400,423,-27,126,-1054,1222,-786,-308,1371,-993,-189,-319,353,363,-337,-184,342,242,-70,-507,-287,666,286,-721,109,0,255,136,-688,978,-87,-992,707,-367,-32,-52,462,-82,-93,491,-874,335,304,213,-709,57,473,-542,325,-72,257,-27,-507,219,385,-362,-237,291,-511,888,-265,-453,790,-340,-818,931,422,-257,-127,-718,1187,-518,-618,-281,1018,-435,304,-960,863,-550,150,307,112,500,-266,-581,2,-269,488,-360,423,-453,298,364,-565,217,-176,-210,179,-186,80,343,262,-331,279,-525,242,-404,780,-341,310,-262,-96,72,527,-600,221,-607,667,-1046,1089,-187,-87,133,-452,350,-297,-100,-47,604,-656,449,514,-858,253,48,-442,796,-192,-254,-460,192,201,-158,412,-216,521,-596,-209,576,-44,-789,540,23,-84,-453,754,-440,171,-777,321,577,-170,420,-396,-8,136,-593,443,597,-1419,859,-218,409,165,-592,-164,509,-581,1355,-951,410,-524,577,-613,168,-173,-319,865,-361,-484,764,60,-584,-272,560,458,-683,578,-721,282,-146,363,-505,442,134,-330,252,-241,-344,303,186,-164,570,-963,617,133,-661,198,703,-282,-178,-228,295,-228,308,-117,-178,-476,42,703,-24,-479,-184,119,833,-781,566,-222,-282,569,-664,373,-316,528,158,-751,447,292,12,-719,181,-316,-173,-12,1117,-1257,436,375,-457,3,81,702,-335,219,-271,-653,-220,399,179,541,-338,132,410,-1370,1633,-1075,61,169,-507,841,-966,-82,538,-29,-282,1222,-1111,574,-383,450,14,-639,651,-860,827,-61,-637,101,157,-161,478,-867,896,392,-1083,246,433,4,-487,-154,476,-895,1317,-793,638,-43,-993,849,-195,-14,-15,437,-25,11,-329,-89,227,-37,-540,888,-389,-848,732,-460,533,282,-609,12,180,290,-84,562,-1107,390,30,-490,-8,428,-359,-80,571,439,-1322,365,651,-542,725,-236,-287,-75,-29,343,-161,-314,314,-163,195,-12,25,222,-872,473,-223,414,-972,866,25,-63,-353,480,-572,1311,-1073,129,-170,-90,415,-756,245,701,-409,-106,475,129,-545,689,-990,242,-257,488,-108,588,-852,518,-249,-538,655,-370,220,-340,613,-272,398,-710,229,324,157,-319,627,-599,-235,-94,51,430,109,-842,397,-269,144,568,155,-693,135,232,-1011,514,223,345,-319,171,-66,119,-145,-358,-32,10,845,-814,-508,962,491,-558,-17,168,-388,374,-223,530,-843,97,688,-552,220,-829,563,515,-454,228,-295,-332,769,-623,240,182,226,-235,-263,374,-1155,1283,-117,-387,512,-467,-959,531,1417,-973,-415,-311,110,755,146,-346,511,-268,6,110,-141,11,-58,-253,-224,-608,852,14,-37,-249,320,-94,780,-972,196,25,-350,9,775,-363,142,-286,-231,477,148,-357,-132,10,629,-386,37,452,-178,-825,724,117,-702,190,756,-311,-283,-119,-190,660,137,-878,249,259,276,-451,-263,549,-782,604,389,-707,-299,78,238,-162,441,1,139,307,-411,-457,263,462,-446,-104,-535,1194,-638,28,437,-243,345,-480,-930,592,479,195,-321,-287,386,-453,660,-359,-707,1297,-693,-76,299,378,-465,-710,900,1,-682,346,-268,742,-146,-212,-159,687,-272,61,-97,-722,910,-234,102,0,-674,-230,871,-593,227,-7,167,-198,-403,512,169,-359,-46,495,-620,1069,-709,-171,-236,19,171,348,-525,234,-144,563,461,-957,-40,157,377,-176,76,-199,-544,68,341,-17,147,-144,-202,438,298,-349,-318,171,240,-434,-103,342,-66,28,118,-132,579,-13,-149,-79,-50,-468,-287,387,270,416,-992,1191,-955,6,384,-637,160,43,-331,181,562,-637,529,248,-939,610,137,-698,1166,-339,-283,-573,552,-181,387,-611,431,95,-281,267,-459,160,633,-1234,940,-174,-53,-577,148,543,-257,-9,971,-975,126,-380,386,-107,-64,-291,735,-246,-338,243,-15,-48,108,-391,537,-484,520,-405,274,-93,408,-566,-339,1021,-394,-134,156,-202,377,-106,-1236,1306,140,-231,132,-365,95,-190,-370,223,162,-155,901,-1404,971,-513,611,-373,-74,95,-375,686,-308,414,-600,937,-1569,974,-729,658,357,-673,21,443,-653,718,-507,-116,309,243,65,-317,-436,-87,423,-395,255,918,-765,446,-499,-451,438,61,739,-553,420,-125,-529,544,-328,29,21,-96,-366,402,377,-393,67,-664,1069,-372,136,-537,482,-686,249,-150,-78,320,306,-467,29,549,43,-210,-348,149,358,-240,253,-211,-492,346,24,-132,488,-268,-708,950,-304,-2,243,-367,-55,-321,-76,-360,598,-253,351,-158,428,76,-362,-942,1212,156,-852,730,-1272,744,497,144,103,-500,60,-33,-403,985,-1161,490,-374,242,-138,577,-518,-705,1221,-490,273,-229,-49,935,-1246,719,-346,-347,713,-581,574,-307,-163,-91,482,-491,297,4,-78,447,-557,-100,57,212,64,196,-106,-55,385,-513,-5,510,-682,385,-1058,1984,-1414,-74,1133,-1199,469,-607,1063,64,-535,543,-262,-59,86,-149,-154,-487,565,-639,800,-289,-4,305,-506,-229,424,-197,-85,-23,898,-818,55,561,-314,595,-412,-198,57,116,-221,-2,-216,223,-6,-140,527,-843,-160,380,478,46,-387,196,-341,13,3,-38,459,-138,413,-1137,1024,-763,736,-575,66,167,14,-783,1339,-632,-455,749,-231,144,-365,-28,34,807,-1322,1112,-274,-398,-67,586,-232,-303,475,-517,472,-23,39,11,121,-507,-358,331,547,-46,-769,475,-479,681,393,-651,25,140,-447,-58,353,83,-784,408,464,61,-165,-314,401,-142,-6,157,312,-845,-433,1161,-218,-758,238,189,109,-23,-147,-131,78,552,-381,-271,1177,-1532,570,140,-194,217,-237,-256,365,-174,347,-12,-36,-658,531,656,-322,-290,-8,-514,99,485,-297,131,-583,510,387,-183,-257,493,-636,-18,49,104,-320,208,254,-507,463,161,-344,248,-718,1313,-412,-449,-18,629,-484,528,-504,509,-913,612,-3,-49,75,-487,24,-160,165,859,-52,-813,289,97,-536,656,163,-813,477,596,-306,-253,-124,-559,92,903,-518,231,529,-496,-57,143,-437,-204,137,2,24,-557,1603,120,-1079,246,-599,936,-1011,797,25,-289,-246,-136,394,-757,1091,-174,-115,68,-175,43,-249,466,-33,-518,179,-95,505,-585,584,-174,87,-746,453,-279,718,-149,-596,-136,873,-168,-608,548,-228,687,-741,128,-95,46,-264,257,560,-899,301,-341,286,430,254,-925,461,257,-310,-239,825,-793,-209,157,315,70,-522,487,-156,-569,614,-119,-228,357,31,15,98,-119,-77,30,-370,229,75,313,-193,-386,658,-1328,1467,-365,264,-718,318,-122,-1090,1506,-184,-229,388,-116,-224,-231,198,510,-643,324,-538,517,36,165,-406,-17,390,-171,-198,-392,610,-262,242,16,-182,-121,354,-306,-325,656,-487,118,-136,-299,276,-252,65,979,-272,-407,-371,676,-112,-618,439,633,-656,481,-752,964,-203,-580,638,-818,346,328,-513,72,-319,336,293,-469,111,807,-825,230,125,-25,-70,-805,250,1279,-449,-929,353,341,-614,-337,992,431,-220,-1032,1165,173,-726,-68,-504,316,152,348,7,-123,-93,-417,216,440,-322,333,-823,946,131,-339,100,-41,-445,310,166,47,-559,546,-949,274,1027,-775,131,108,-145,-153,249,-216,130,-348,628,-622,460,-577,244,-73,922,-235,-1136,383,17,-54,111,-105,219,-208,512,-19,91,-544,468,431,-117,-847,504,-208,226,-1524,791,483,-162,231,-351,823,-417,658,-1247,134,114,-114,51,962,-869,587,-283,-633,812,-403,335,-736,736,-478,485,-399,582,-872,635,85,-342,-34,-5,-234,41,370,-839,336,175,585,-721,145,545,-182,39,-565,831,-464,-955,686,447,-830,467,269,149,-201,559,-919,394,-184,-358,237,-156,373,-239,-75,516,309,-1086,780,-1075,574,403,144,-338,155,-245,-36,-279,142,-175,79,672,-843,468,-278,256,-373,705,-355,-63,-173,842,-911,292,57,-393,79,477,-685,1058,-907,-57,288,-12,260,219,243,-1033,-277,1164,50,-621,-291,347,-101,97,236,-438,627,-881,989,-546,288,-902,566,586,-153,106,-404,-91,-146,72,34,227,-702,53,848,-371,-26,498,15,-136,-352,137,-273,-126,-352,684,133,187,23,-508,-48,163,197,-546,27,51,270,95,-99,-451,911,-259,-655,221,423,-424,378,349,-547,333,-24,-488,384,-388,-142,-75,114,-54,806,-573,202,-338,586,-538,-76,680,-642,383,-293,407,-620,289,-72,20,414,-728,328,517,20,290,-1564,1126,-329,-97,273,-799,715,329,-309,444,-574,-135,365,-131,-56,258,-835,231,-287,131,466,-343,630,-733,520,-443,21,294,402,-813,102,76,421,-466,167,691,-538,254,-400,-6,-447,957,-336,284,-552,-844,1677,-682,-335,-178,501,-192,137,318,-159,254,-539,-71,93,43,-63,57,275,24,-669,391,79,270,-598,831,-1194,845,-388,417,-691,-400,1273,201,-1006,733,-191,-53,-123,-198,618,-58,157,-365,-286,223,-399,148,-162,433,-326,-116,-56,137,279,-268,384,69,240,-330,301,-328,-770,178,471,-289,1089,-895,-6,-384,154,427,393,-612,-216,-60,-180,835,100,-599,470,-653,738,-114,-161,706,-931,-23,77,211,397,-872,290,-211,696,-478,-343,745,-431,128,7,4,3,226,-609,346,-349,718,-218,-228,69,-513,677,-534,544,-549,344,-737,599,270,-577,614,-222,587,-441,583,-1383,663,-295,982,-923,25,-238,544,-179,-50,-90,351,-312,-120,-346,435,334,-509,505,-256,-29,975,-1163,14,905,-960,608,-526,128,209,-169,423,-926,1107,-575,47,0,85,266,-855,380,-54,45,198,31,-39,259,375,-590,-160,-148,-314,306,171,-131,232,169,-536,711,-273,-160,-688,1112,-555,100,-299,452,-716,941,-618,245,172,-153,-275,218,-44,491,-143,-842,1181,-790,76,81,-156,7,168,-851,997,-740,886,-301,180,-810,566,-643,1075,88,-818,149,-7,176,406,-161,-150,-306,1332,-1042,-1147,1865,-767,-101,90,-283,192,705,-580,-1045,759,-59,20,-9,184,-107,-131,93,932,-1184,890,-508,511,-589,268,-211,-466,621,-1023,780,8,109,-17,528,-63,-768,578,339,-253,-58,-445,-441,171,807,-510,101,323,-163,-319,816,-239,-779,552,-897,762,608,-717,-401,1236,-502,-790,286,97,220,-395,1142,-1283,-40,75,174,-46,568,-564,735,-163,-482,742,-334,-512,555,-482,-41,-26,4,304,322,-165,-51,129,75,-750,276,-351,-245,275,450,538,-1008,45,559,769,-656,-541,338,-415,452,-72,-687,342,507,-368,206,124,-212,-480,-187,748,34,-190,-447,398,906,-883,170,-216,639,-447,-87,166,-672,589,-337,7,150,-144,-229,1312,-695,-1078,1285,-721,249,-106,338,-359,348,-813,456,481,-228,627,-951,449,-32,47,-167,172,12,9,-142,359,-643,590,-221,-83,-498,344,487,-434,522,-1045,670,144,-699,1213,-424,-459,311,-394,319,-207,-637,796,-407,388,323,-1054,385,267,367,-699,609,-856,650,-8,197,-372,392,-813,224,341,-113,-1059,1013,-273,-429,1090,-356,367,-344,331,124,-1202,488,654,87,50,-573,14,-437,237,-300,716,-51,-204,-278,178,-136,-294,879,180,-421,-121,-183,277,109,-14,-391,-1,-119,-295,279,649,-396,2,-229,292,265,-143,-673,380,134,-185,663,-403,-434,42,272,-62,-97,421,-684,1066,-133,-156,-31,-302,11,213,-78,-291,237,396,-425,-125,-254,702,-145,-10,363,-511,-488,567,-363,447,200,-621,355,67,-58,-683,528,-440,144,-253,507,-62,-404,708,-72,85,-460,235,394,-187,-540,509,-891,1448,-630,-540,299,-569,711,-170,-124,398,43,163,-390,174,-503,348,-504,258,851,-1384,885,-108,-429,836,-127,-60,-486,150,131,-846,618,-48,-57,577,-687,461,80,328,-499,153,152,-558,766,-540,258,67,-986,387,825,-1018,806,-558,456,-583,565,-68,-300,585,-374,-374,198,52,-377,-108,150,136,-11,256,-556,60,386,77,230,-290,17,-255,192,487,-708,-280,884,-638,699,317,-216,-431,295,-538,393,78,-139,-803,1263,-857,262,204,-54,-506,251,-162,149,131,682,-404,-823,768,-641,864,-851,438,76,-169,-97,112,37,-121,455,-284,-327,587,-34,-257,-52,20,-173,-321,-28,516,-355,-542,1702,-1131,481,-681,992,-944,459,98,-998,1008,-202,-535,380,266,-806,6,605,409,267,-970,733,-1081,737,-151,408,-653,645,-1101,796,581,-592,392,-512,336,302,-1160,1243,-621,64,-438,234,655,-713,445,40,-976,456,685,-287,-428,249,-169,419,-519,219,-276,956,-1184,286,712,-431,58,208,-303,-25,771,-560,-579,907,-565,300,-396,229,-171,-345,776,-230,-84,-250,472,-37,78,-250,51,-256,-240,1084,-387,-303,-425,769,-702,798,-28,-359,70,-542,426,-204,740,-881,664,-41,-561,389,-557,944,-68,-327,24,-115,-217,-316,952,-508,34,2,35,97,-499,524,-258,273,-4,-290,-147,620,-44,-36,-1011,303,-126,984,-830,325,-274,715,-480,-187,107,114,191,-307,455,-343,-308,458,278,48,-833,277,-99,186,425,-118,-142,-38,758,-907,-12,9,332,-838,313,532,-556,269,-136,-136,33,-28,-743,1361,-661,-52,411,-268,95,-446,269,439,-56,-305,-256,870,-400,-152,-77,-158,551,331,-571,80,112,30,29,-405,-86,-701,691,214,-10,-620,890,-121,-181,378,-42,-228,148,-160,144,-541,640,-943,843,-83,257,-27,-436,-316,1083,-810,456,-606,167,-150,840,-762,-299,176,111,864,-158,-895,1218,-1107,-385,784,-149,-78,81,518,-539,-490,753,-174,-158,426,-892,868,-224,-89,-268,347,224,36,-112,-289,-667,566,15,-289,507,22,224,-659,140,-238,288,145,879,-1792,184,507,-162,899,-343,417,-887,938,-850,-182,40,-337,752,165,-556,747,-492,80,-575,522,595,-669,212,397,-924,989,-360,-749,382,-308,152,103,243,-1076,963,225,-119,-607,270,413,-91,6,-464,323,-441,778,-584,-6,600,-528,641,-601,496,-167,-92,-32,-203,287,-453,499,-85,672,-568,-139,-148,69,174,-195,-433,72,132,843,-288,-877,272,482,-596,10,183,380,-101,-550,90,64,328,-333,454,73,-459,212,-296,638,-353,658,-863,431,-855,127,276,-203,827,-848,202,27,427,-602,1010,-987,200,-352,52,276,167,273,-494,246,195,-510,582,-83,-73,-281,-299,376,296,-99,-28,-788,682,-114,181,-637,815,-211,152,95,-883,127,1243,-1007,331,-101,-69,-207,480,268,-372,-191,-146,476,-485,193,150,-393,89,204,298,-451,11,-182,-272,459,215,633,-1085,270,-136,624,-190,-279,-433,510,15,-350,24,207,-441,372,526,445,-1184,545,315,-1172,476,325,-826,422,1244,-1490,48,-332,774,13,-85,486,-584,-164,720,-503,54,-81,594,-295,-465,302,-353,252,-334,88,-274,271,223,375,-515,136,-131,423,-378,-310,327,255,-23,-130,47,666,-1167,305,276,-479,-203,725,419,-457,-373,-246,544,249,-431,45,596,-550,246,-737,788,-458,262,181,-388,-405,529,682,-603,-313,1,-244,5,908,-568,280,169,403,-1024,-252,1251,-226,-1639,763,29,175,-92,286,70,-94,-410,836,-541,-157,-29,-247,753,-276,37,-70,-159,802,281,-1155,239,-40,284,219,-420,-549,1002,-1066,351,303,-62,-35,143,-859,1139,-1389,1374,-236,-380,748,-405,-245,-272,361,-74,189,608,-915,377,-58,-123,-416,500,-341,28,615,-644,243,19,696,-740,310,-51,-218,96,182,-452,75,-16,-95,243,-73,-309,164,9,-248,30,589,16,397,-836,341,4,-185,520,-391,-243,723,-659,436,-327,-188,-657,826,-58,-512,-144,596,366,-217,101,-156,35,-568,866,-764,489,-390,538,136,-695,238,-71,455,-378,-442,-120,672,-92,-712,868,-696,548,486,-440,46,-144,-646,308,-4,78,569,-478,476,-410,-77,822,-454,-58,-53,146,54,-200,434,-930,800,-4,-404,249,-486,605,-574,103,239,-209,224,-178,-731,745,289,-234,-167,77,97,347,-151,-463,225,-684,1344,-635,161,-174,113,72,198,-725,217,267,-445,197,614,-933,1099,-563,-74,-118,-34,202,-515,838,-190,-178,135,-571,482,-100,-188,205,-74,-266,-507,777,459,-138,-499,376,115,-180,-358,513,-526,375,-330,295,-50,-696,1212,-724,814,-1294,403,739,-823,321,191,-491,1109,-378,-748,-170,783,-158,351,-216,-930,378,239,142,-436,-185,146,989,-607,-344,384,63,42,-561,551,-111,-7,-418,399,330,-1106,1195,-186,-92,-5,-568,166,-272,51,405,-16,34,115,-222,-729,1290,249,-892,-426,732,-697,717,-199,215,-677,-43,440,340,-436,384,-46,-540,308,389,-228,-119,-554,26,560,-259,-81,531,76,-211,-355,348,43,-684,609,-192,-494,924,-369,64,244,20,-330,242,-78,-401,656,-455,-527,690,-167,-95,-250,331,181,337,-697,-11,97,876,-1126,206,32,28,493,-398,-493,759,-431,-227,259,429,193,-62,-254,-373,334,258,-292,-373,242,-123,396,84,134,-446,207,29,-649,74,879,-848,-5,-175,85,397,362,-195,-153,-471,682,-678,553,-345,-528,1321,-808,-123,-29,-197,594,-202,343,-294,598,-454,-499,196,425,464,-845,316,-321,979,-1285,693,-316,404,37,-803,901,-189,-336,375,-413,43,377,-200,-504,51,630,-306,-237,815,-114,-381,75,-203,-588,488,-286,878,-36,-267,-435,1009,-1434,1134,-411,94,-409,232,196,347,-553,418,-417,-21,124,111,-320,474,-416,340,-445,432,325,-373,-281,4,-53,461,-725,49,477,361,-762,890,-1001,730,-461,627,-75,-480,-158,189,-414,-10,366,240,-280,-214,-140,812,-601,533,-249,-146,206,-113,-51,-168,91,-262,415,-249,-119,394,-361,781,-141,-670,20,321,-64,242,-242,306,220,-509,17,60,-188,-2,242,-285,-342,171,536,-419,144,284,-176,-402,-608,970,182,-440,252,307,-542,1107,-1466,-116,964,-159,-322,142,-167,935,-827,238,-545,834,-717,245,383,-315,-361,207,397,0,305,-623,420,-295,-50,-284,74,106,334,-760,674,-179,-32,11,191,420,-529,-388,859,-832,249,-432,882,-346,-177,-172,585,-417,9,600,-834,312,-63,-559,497,283,450,-372,-966,827,-6,318,-606,-142,653,-498,2,-103,-152,562,17,456,-1073,273,106,-232,604,-399,-106,921,-1000,-48,619,464,-1230,346,431,-510,-10,64,674,-507,-146,-1,-79,82,-151,279,349,124,-847,-234,1426,-1244,725,-203,-63,-395,88,91,427,-479,829,-435,-276,-206,515,96,-298,-437,804,-560,211,124,103,204,-926,-19,828,-51,-884,871,33,-362,402,-284,-90,13,284,-652,202,137,323,-487,70,-433,731,-18,-255,60,623,-803,-156,77,-153,-218,645,276,-808,604,-553,-69,551,126,-647,517,-158,382,-231,77,-797,630,-296,358,-149,716,-777,733,-520,327,-416,-402,162,411,88,-353,16,-35,-56,440,91,-918,920,-870,797,-979,547,-51,-44,525,-293,-83,-82,180,263,-488,-102,679,-422,-223,340,-291,305,-80,-275,565,-1197,1127,116,-299,-37,-483,680,68,-360,112,-107,334,-726,-446,606,-130,570,233,-426,-770,278,227,548,-77,-370,-383,1176,-609,430,-176,-607,161,18,527,-750,351,23,-47,484,-165,12,-71,161,-686,338,-229,-13,80,279,376,-1346,1234,-809,200,-322,1023,-931,618,-350,471,-226,-49,-288,446,241,-740,869,-1147,-48,69,396,-288,396,-92,-464,363,756,-620,-208,-63,243,226,2,-343,-76,623,-184,-440,-223,551,286,-815,785,-92,-856,812,-569,359,380,26,-958,839,-26,-325,387,-710,307,-37,271,92,-178};
bool notp[maxn];
void shai() {
    for (int i = 2; i <= 1000000; ++i) {
        if (!notp[i]) {
            p[cntp++] = i;
        }
        for (int j = 0; j < cntp && i * p[j] <= 1000000; ++j) {
            notp[i * p[j]] = true;
            if (i % p[j] == 0) break;
        }
    }
    for (int i = 1; i <= 1000000; ++i) {
        notp[i] = false;
    }
}
ll pi(ll n) {
    ll k = n / 10000000, ret = 0;
    for (int i = 0; i < k; ++i) {
        ret += buck[i];
    }
    ll L = k * 10000000, l = L + 1, r = n;
    for (int j = 0; j < cntp && p[j] * p[j] <= r; ++j) {
        for (ll k = (l + p[j] - 1) / p[j] * p[j]; k <= r; k += p[j]) {
            notp[k - L] = true;
        }
    }
    for (ll j = l - L; j <= r - L; ++j) {
        if (!notp[j] && j + L != 1) ret++;
        notp[j] = false;
    }
    return ret;
}
int main()
{
    cin.tie(0)->sync_with_stdio(0);
    shai();
    int z;
    cin >> z;
    for (int i = 1; i < 10000; ++i) buck[i] += buck[i-1];
    while (z--) {
        ll n;
        cin >> n;
        ll p1 = pi(n), p2 = pi(n/2);
        cout << (n - (p1 - p2)) / 2 + (p1 - p2) + 1 << '\n';;
    }
    return 0;
}

Compiler Output Limit Exceeded