Problem: Polycarpus has t safes. The password for each safe is a square matrix consisting of decimal digits '0' ... '9' (the sizes of passwords to the safes may vary). Alas, Polycarpus has forgotten all passwords, so now he has to restore them.

Polycarpus enjoys prime numbers, so when he chose the matrix passwords, he wrote a prime number in each row of each matrix. To his surprise, he found that all the matrices turned out to be symmetrical (that is, they remain the same after transposition). Now, years later, Polycarp was irritated to find out that he remembers only the prime numbers pi, written in the first lines of the password matrices.

For each safe find the number of matrices which can be passwords to it.

The number of digits in pi determines the number of rows and columns of the i-th matrix. One prime number can occur in several rows of the password matrix or in several matrices. The prime numbers that are written not in the first row of the matrix may have leading zeros.

Input

The first line of the input contains an integer t (1 ≤ t ≤ 30) — the number of safes. Next t lines contain integers pi (10 ≤ pi ≤ 99999), pi is a prime number written in the first row of the password matrix for the i-th safe. All pi's are written without leading zeros.

Output

Print t numbers, the i-th of them should be the number of matrices that can be a password to the i-th safe. Print the numbers on separate lines.

Examples

Input

4
11
239
401
9001


Output

4
28
61
2834

Note

Here is a possible password matrix for the second safe: 
    
    
      
    239  
    307  
    977  
    

Here is a possible password matrix for the fourth safe: 
    
    
      
    9001  
    0002  
    0002  
    1223   
    

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MX = 100000;
int d[MX + 10];
vector<int> p;
vector<int> ls[100010][10];
map<vector<vector<int> >, int> M;
int go(vector<vector<int> > a, int k) {
  int n = (int)(a).size();
  if (n == k) {
    return 1;
  }
  int tk = 0;
  vector<int> g;
  int ans = 0;
  for (int i = 0; i < k; i++) {
    tk = tk * 10 + a[k][i];
  }
  if (k == n - 1) {
    return (int)(ls[tk][1]).size();
  }
  vector<vector<int> > a1 = a;
  vector<vector<int> > a2;
  for (int i = k; i < n; i++) {
    a2.push_back(a1[i]);
  }
  int tt = M[a2];
  if (tt != 0) {
    return tt - 1;
  }
  for (int j = 0; j < (int)(ls[tk][n - k]).size(); j++) {
    g.clear();
    int x = ls[tk][n - k][j];
    for (int t = 0; t < n - k; t++) {
      g.push_back(x % 10);
      x /= 10;
    }
    reverse((g).begin(), (g).end());
    for (int t = 0; t < n - k; t++) {
      a1[k][t + k] = g[t];
      a1[t + k][k] = g[t];
    }
    ans += go(a1, k + 1);
  }
  return (M[a2] = (ans + 1)) - 1;
}
void obr(int x) {
  int tk = 1;
  for (int i = 0; i < 5; i++) {
    ls[x / tk][i].push_back(x % tk);
    tk = tk * 10;
  }
}
const int a[8363] = {
    1607029, 1755692, 1250842, 1364989, 1393926, 1141975, 1247971, 1286779,
    1397331, 1396686, 1256244, 1629683, 1371558, 1279422, 1143880, 1234952,
    1227031, 1097475, 1165811, 1042850, 984149,  1162885, 1168054, 1309578,
    1242379, 1177512, 963917,  1167534, 1046787, 911097,  1137579, 1142186,
    992466,  1525636, 1517597, 1275646, 1218537, 1187614, 1187363, 972576,
    1151885, 937500,  973174,  1088513, 972313,  962807,  1049632, 1148145,
    1102679, 903402,  985267,  1045176, 887149,  854129,  946520,  1459995,
    1224501, 1046573, 1135189, 982861,  853066,  932147,  854251,  1392479,
    1140912, 1167973, 910837,  1086389, 971817,  1044633, 854968,  988527,
    809913,  809900,  996801,  1276206, 1201915, 1136540, 1019901, 1111570,
    991690,  1066492, 1045183, 1017709, 907580,  913253,  1081794, 886557,
    859037,  1042672, 934904,  987411,  808378,  988757,  886115,  988298,
    1394074, 1247473, 889751,  970463,  939525,  853579,  1024541, 913740,
    811746,  992434,  1628066, 1070709, 1009549, 1005391, 1097551, 1040123,
    1195445, 1164257, 953148,  1167555, 1150887, 942822,  1030363, 1070692,
    929491,  921885,  976663,  1005432, 1012035, 826770,  808448,  1095573,
    904950,  985719,  977898,  802294,  929011,  956336,  855931,  761463,
    839002,  1073191, 881245,  1021204, 913898,  962776,  957905,  816311,
    906109,  909849,  816859,  1036076, 984570,  793918,  933685,  765554,
    723554,  908328,  876091,  783452,  887965,  729515,  1218194, 923167,
    803293,  831119,  921260,  805977,  715314,  874345,  718887,  802357,
    929779,  912112,  717677,  701455,  827549,  741068,  749938,  1195821,
    828767,  900965,  933481,  904246,  721376,  783561,  850527,  760472,
    1164564, 956424,  978821,  932707,  765676,  909656,  912550,  816232,
    832304,  682459,  680661,  684132,  1164405, 1042315, 933554,  766510,
    911473,  811120,  877970,  875821,  782328,  743282,  852363,  830161,
    680095,  1285515, 1310826, 1000480, 1180838, 1182980, 1056134, 1144629,
    1149141, 916899,  1305964, 1072611, 1168086, 1094427, 979561,  990973,
    884647,  803298,  931633,  929279,  767776,  1245217, 1045383, 814331,
    863781,  938208,  930584,  932166,  888313,  794326,  749008,  887012,
    792386,  1213844, 966347,  866557,  920040,  756000,  891825,  733138,
    796451,  866560,  1170839, 1048799, 983948,  935096,  918749,  754672,
    880300,  723192,  866696,  775647,  684171,  839754,  691671,  1166664,
    982649,  806403,  765484,  813606,  882169,  723816,  877270,  745250,
    702642,  832721,  744486,  1114052, 932902,  934439,  836806,  713933,
    838816,  690800,  836064,  748338,  815443,  708317,  654413,  1138743,
    957207,  914243,  792648,  862645,  704101,  811977,  815205,  816999,
    728526,  998002,  884931,  886127,  795984,  838032,  834289,  709218,
    790575,  710065,  915586,  928426,  764013,  831212,  885309,  837131,
    831710,  743287,  649406,  817810,  729719,  792975,  1510566, 1515911,
    1232449, 1360770, 1186035, 963973,  1150498, 1028868, 1081214, 1082184,
    974643,  1271382, 1142869, 1018388, 830934,  788243,  956914,  860049,
    910546,  935521,  765279,  909097,  741301,  835856,  918893,  872739,
    918289,  825698,  821215,  709430,  866573,  709817,  1062798, 994408,
    774211,  922395,  753676,  826011,  691426,  846033,  690158,  759349,
    959485,  783367,  913399,  866890,  859500,  702266,  814816,  732261,
    687715,  664149,  737158,  957323,  909985,  724387,  860255,  664639,
    682074,  811940,  665031,  914543,  820174,  710607,  850279,  738852,
    695524,  716492,  775777,  633818,  777367,  775875,  637417,  995034,
    935750,  889753,  886528,  796881,  836106,  682769,  749521,  791969,
    793954,  708804,  712428,  878872,  778509,  840921,  817154,  732703,
    797546,  647594,  713604,  774421,  1082225, 1087574, 885174,  908850,
    867234,  843576,  850865,  772790,  630533,  633527,  697516,  1306432,
    1230024, 1050377, 1145810, 1100018, 905652,  1072524, 1042978, 1045139,
    858613,  1006273, 933503,  836161,  927741,  829724,  907939,  746778,
    729098,  961578,  939256,  888191,  796245,  883094,  836856,  840400,
    1136336, 916901,  915623,  756252,  868774,  715332,  734589,  671951,
    728388,  1103492, 907138,  934146,  834976,  884595,  869576,  716593,
    691942,  752652,  794067,  732944,  703657,  1094740, 833480,  861322,
    706788,  835297,  749341,  829889,  682820,  788762,  788170,  789482,
    789158,  837390,  689753,  751977,  820006,  731933,  789494,  649178,
    669665,  746971,  674551,  902540,  747736,  860193,  839719,  690109,
    815140,  671116,  806916,  723208,  636923,  789119,  705037,  764924,
    637916,  878973,  838718,  689370,  817766,  793626,  790030,  616974,
    671376,  691012,  613804,  749009,  616042,  840476,  753720,  730083,
    649900,  786888,  647096,  669350,  748554,  1225940, 1011783, 1140291,
    1096729, 1044334, 1075514, 883871,  1043069, 1047014, 1229167, 1012020,
    980450,  960885,  792816,  858208,  832434,  876962,  905906,  719002,
    876559,  788678,  811620,  768920,  911726,  882401,  783972,  835275,
    745676,  855865,  705610,  686640,  745192,  749226,  942672,  955465,
    856887,  816012,  891057,  771857,  765508,  818138,  838266,  692138,
    811375,  817337,  1104446, 925410,  727995,  771771,  835781,  832505,
    788778,  650605,  813780,  787743,  653771,  925283,  723685,  829694,
    825689,  738456,  701988,  784473,  782473,  1045495, 860713,  785544,
    748409,  788895,  791344,  649743,  707713,  745027,  612125,  766719,
    687610,  745523,  707416,  837849,  835031,  691466,  743402,  724952,
    770243,  633382,  785869,  630138,  768970,  634287,  1043293, 935414,
    722298,  833142,  701712,  632982,  746289,  612948,  665826,  1050622,
    863724,  872662,  780698,  833738,  670713,  699028,  768058,  770155,
    747539,  1390741, 1139248, 1084768, 852557,  989515,  989311,  810749,
    884439,  1020721, 811800,  991532,  814518,  1163803, 976449,  763853,
    815555,  879991,  830741,  678300,  740920,  833270,  766943,  886795,
    795884,  861777,  752876,  833024,  649784,  814241,  1084843, 816348,
    846110,  754530,  734928,  775232,  774320,  693931,  772552,  880913,
    722595,  838503,  688001,  821899,  651058,  787690,  788716,  633485,
    746171,  611003,  750794,  789179,  748602,  647111,  785434,  745050,
    611602,  767532,  991673,  812772,  746684,  773792,  775938,  671658,
    743512,  608859,  705673,  729016,  710312,  707398,  637219,  1018826,
    729656,  770326,  632597,  683089,  727215,  594908,  830358,  794980,
    713508,  773414,  752184,  726368,  654502,  708301,  633495,  993768,
    993039,  793749,  650835,  771101,  634033,  749151,  705845,  651126,
    706891,  579064,  705856,  1191048, 1134490, 934275,  1019504, 1112169,
    1070804, 883119,  1069778, 858063,  1014001, 911499,  984999,  826395,
    956032,  771947,  805719,  706231,  851983,  761414,  855271,  1138271,
    939928,  1021476, 886174,  793998,  704946,  811813,  814469,  732752,
    771672,  891438,  734618,  868951,  844314,  840220,  750584,  675612,
    792667,  654076,  708676,  793478,  1072747, 742857,  809102,  840645,
    814322,  729957,  633869,  791548,  653672,  764097,  682824,  770606,
    635800,  960213,  809424,  747794,  803320,  686890,  787036,  705727,
    762968,  627400,  690023,  912674,  814727,  669779,  629939,  686676,
    650969,  724783,  726550,  859162,  875080,  746693,  670049,  651060,
    704997,  748754,  741525,  662653,  745185,  836737,  667385,  652536,
    710970,  764241,  725318,  723555,  723355,  1020948, 913079,  851990,
    816367,  817069,  732336,  710566,  628275,  684548,  747035,  615551,
    727613,  596169,  648812,  1167554, 1051930, 1052422, 862303,  941305,
    936137,  991556,  836138,  885947,  815104,  878583,  933624,  766449,
    913955,  913840,  883738,  791183,  744837,  829291,  836394,  749836,
    933998,  766774,  887031,  796952,  866909,  833691,  834342,  682000,
    710112,  648217,  707915,  1092951, 893995,  914376,  909479,  780367,
    825297,  816913,  636689,  798947,  713006,  636628,  1053392, 878754,
    687829,  820844,  734595,  793433,  790447,  645279,  748440,  746668,
    748349,  1044097, 718849,  834339,  832734,  727132,  786646,  784973,
    742344,  608084,  741963,  682512,  635793,  704941,  726294,  652074,
    710820,  1024540, 851946,  765014,  794707,  767785,  687408,  626565,
    745355,  595627,  723543,  598737,  993699,  694683,  669703,  633356,
    633590,  831719,  832061,  680999,  745433,  613172,  667625,  730681,
    650501,  1391045, 1246094, 1165963, 1079343, 886451,  1038532, 886429,
    1023174, 913688,  986679,  808904,  931976,  814932,  880940,  717850,
    833395,  828913,  829236,  914583,  932418,  933835,  836341,  861277,
    707802,  752043,  745593,  651754,  815517,  706944,  1087194, 970165,
    814213,  845168,  797829,  711919,  771836,  633270,  774444,  1044469,
    724598,  840022,  836394,  690227,  750817,  821747,  794279,  654152,
    648733,  749369,  671963,  773100,  637258,  744772,  665937,  1041246,
    856468,  808592,  785244,  788332,  780243,  699558,  760929,  627212,
    740165,  610966,  991429,  890476,  706670,  703167,  577424,  583400,
    637404,  912855,  703563,  668615,  705244,  765066,  761036,  682112,
    728732,  614389,  727178,  992550,  832342,  745239,  747203,  750264,
    744262,  707291,  580239,  630863,  705253,  832184,  742816,  654254,
    635575,  670443,  707517,  709232,  731771,  652939,  708679,  708107,
    583687,  1642544, 1563949, 1563816, 1400424, 1209842, 1468076, 1393792,
    1431231, 1247792, 1634767, 1339119, 1371962, 1123513, 1305781, 1170192,
    1238336, 1013740, 1108716, 1166649, 1204287, 984149,  1163577, 1557468,
    1174749, 1208636, 1213861, 1055061, 1110333, 995640,  908093,  912676,
    1215504, 998060,  1187363, 1152652, 944512,  1142701, 937500,  1023572,
    973174,  966759,  1084229, 972313,  1204532, 1233340, 1149052, 1110345,
    1110346, 887149,  967427,  1041782, 1196026, 1309767, 1165988, 1139727,
    1104801, 991472,  1094988, 1041042, 1040858, 940897,  1167357, 910837,
    971817,  1050262, 988527,  990417,  992059,  1173686, 985323,  1072284,
    1111805, 1076383, 887109,  965434,  1066492, 956408,  1045183, 1044849,
    907580,  1138381, 1248499, 941068,  852501,  1021077, 914641,  808577,
    809900,  889847,  1394074, 1113140, 998058,  970463,  858796,  931753,
    990915,  992388,  994103,  1631654, 1370423, 1371142, 1125003, 1226777,
    1305509, 1271738, 1097551, 1163050, 953725,  1038740, 1365813, 1120258,
    1094354, 958829,  1038627, 929491,  844605,  978793,  876227,  902751,
    798812,  982702,  982409,  1095827, 1040360, 854399,  807169,  833992,
    783680,  927742,  1067661, 881245,  958709,  1019363, 966214,  792749,
    769575,  837204,  906109,  913704,  750018,  1229830, 1007834, 927755,
    965591,  723554,  876757,  717770,  887965,  883952,  797402,  1218194,
    845819,  979444,  979041,  878273,  754296,  826010,  875102,  783532,
    735888,  715314,  781389,  789402,  1160868, 977129,  979430,  802357,
    720357,  788893,  829237,  858447,  831267,  1195821, 1004002, 788440,
    768424,  831451,  901782,  739175,  705296,  876706,  700263,  768691,
    1161922, 803950,  932707,  816232,  880809,  878565,  788918,  832304,
    854619,  829852,  831588,  974923,  837182,  745186,  881308,  828428,
    700027,  832033,  684812,  1562355, 1308923, 1023966, 1219037, 1000480,
    1086870, 1172585, 1111038, 913582,  1149141, 1026570, 1116412, 1112129,
    1168086, 1093945, 1041205, 932976,  1022049, 812328,  979934,  803298,
    874617,  958741,  829574,  931659,  889510,  772239,  834864,  908664,
    914587,  749008,  816973,  887498,  887228,  1209623, 998594,  920040,
    821371,  711476,  772777,  864831,  866560,  712054,  1048799, 918749,
    886283,  730372,  880917,  748805,  833069,  833904,  1169786, 982649,
    908857,  882169,  885051,  792335,  684146,  855783,  859814,  934439,
    836806,  887965,  713933,  777984,  841765,  834624,  709161,  732897,
    796164,  654413,  712182,  1019748, 789821,  914243,  750385,  792648,
    863775,  857781,  729594,  688032,  811736,  669155,  914210,  928845,
    763935,  834289,  747981,  790763,  812886,  669844,  1113589, 915586,
    887048,  711083,  839597,  790208,  788932,  817810,  790139,  1515911,
    1270654, 1039511, 1210407, 987852,  1087372, 1059207, 1144438, 1143495,
    930035,  1025026, 1081214, 1108638, 1081969, 884535,  974643,  871947,
    996705,  968297,  860049,  743074,  940562,  813009,  746148,  1211590,
    1216104, 1093003, 792288,  911939,  779648,  799879,  866573,  869763,
    709817,  993878,  947191,  774211,  925053,  826011,  729114,  760356,
    870241,  759349,  783367,  893242,  709030,  771997,  843270,  670884,
    1026671, 885432,  724387,  797801,  775046,  699534,  811906,  813718,
    664639,  812213,  813205,  735899,  1087261, 977944,  869409,  710607,
    781453,  850279,  773873,  695524,  796607,  652720,  633818,  694939,
    837420,  842298,  840725,  689020,  835343,  794921,  649930,  815035,
    708804,  1076048, 908916,  817303,  704175,  840921,  847270,  664028,
    692455,  797546,  713604,  630212,  771262,  694415,  974719,  906441,
    742115,  779503,  665211,  793596,  649523,  774630,  774885,  1456227,
    1199076, 1105139, 1172440, 1050377, 1109688, 993580,  1045155, 1072524,
    884920,  1045139, 1047275, 864055,  1220392, 1006273, 1096984, 1034003,
    983519,  964233,  792938,  925975,  789296,  812130,  874409,  729098,
    1165771, 937781,  841576,  815385,  730534,  883094,  836856,  794500,
    821662,  734992,  772519,  841915,  841330,  752726,  820584,  907138,
    930575,  834976,  888491,  775075,  839620,  711538,  816511,  790225,
    717877,  985600,  765123,  726947,  861322,  685760,  829889,  808590,
    789158,  879164,  839001,  816371,  706601,  767670,  633968,  746971,
    751319,  620091,  956694,  839203,  727323,  769071,  636923,  769156,
    768839,  690115,  936618,  838718,  792655,  652306,  790030,  708047,
    635115,  667397,  860786,  723356,  787245,  840476,  794100,  788969,
    616131,  768694,  633637,  689680,  668261,  1225940, 1140291, 1140391,
    938652,  903916,  1075514, 857438,  861065,  1031147, 848473,  980450,
    809611,  766075,  921943,  873712,  780843,  903944,  874281,  780541,
    880261,  836645,  750714,  885783,  727969,  876953,  835307,  1144889,
    1135949, 942672,  1015847, 913324,  791715,  864248,  771857,  709503,
    672314,  838266,  817337,  984352,  928238,  877215,  771771,  688921,
    828435,  684776,  785747,  703662,  814207,  874793,  706216,  829694,
    786319,  663754,  722509,  782473,  701295,  1045495, 1043455, 934029,
    833250,  816582,  730274,  791344,  646481,  612125,  770405,  687610,
    745415,  1068761, 744400,  835031,  813431,  669808,  716394,  763957,
    787942,  762852,  684047,  1048355, 784809,  790877,  650881,  707461,
    613189,  769153,  665826,  1046114, 872662,  780698,  814154,  816387,
    726585,  790391,  785152,  663203,  747629,  615538,  668355,  1388563,
    956343,  1109891, 992652,  1047911, 1043416, 990610,  890382,  954203,
    976449,  979100,  877304,  879991,  877086,  830128,  853545,  702093,
    830741,  740920,  1111568, 996830,  725887,  707896,  752876,  830690,
    792517,  794161,  649784,  793638,  650147,  969718,  749087,  867666,
    754530,  673375,  667596,  795977,  633579,  772504,  693421,  859940,
    722595,  837042,  822074,  675342,  712829,  706093,  693035,  666531,
    619126,  1045745, 877466,  728851,  641569,  745050,  767532,  745772,
    611520,  649571,  775938,  746627,  612776,  633575,  704954,  706266,
    577570,  707398,  637219,  1019804, 856960,  854601,  703896,  813028,
    729656,  793310,  652082,  683089,  612250,  725342,  992852,  833082,
    792542,  777332,  694790,  673061,  706306,  708123,  654502,  706195,
    706936,  707587,  993039,  793749,  650835,  612808,  742240,  744485,
    665055,  706891,  579064,  705856,  1191048, 981517,  1107649, 1076498,
    957828,  1012791, 835167,  1046698, 858063,  1012895, 1191660, 984999,
    1071389, 789438,  907230,  789937,  855271,  705569,  959135,  793998,
    860349,  856608,  768284,  834168,  690656,  812936,  812809,  732752,
    798590,  716286,  797170,  656873,  655376,  884535,  960133,  708472,
    840645,  694315,  729957,  665385,  709758,  764312,  629295,  960213,
    704492,  769194,  747794,  807749,  803320,  762968,  762430,  853506,
    703150,  794573,  632377,  767447,  750795,  648511,  728115,  599805,
    1043587, 812445,  670049,  723764,  787877,  704997,  784151,  744892,
    616549,  765009,  682805,  745185,  742665,  666475,  1014512, 911567,
    701196,  812686,  667385,  633066,  764241,  723739,  722817,  1020249,
    700423,  764093,  769343,  772705,  631778,  767215,  725966,  596897,
    728392,  597123,  1399182, 1047191, 913456,  1085347, 1045683, 855668,
    886794,  993689,  813369,  815104,  889147,  1048393, 977879,  932553,
    877083,  830080,  829291,  830756,  1116228, 933998,  839222,  796952,
    665732,  727828,  790908,  707915,  649818,  893995,  973602,  818185,
    735361,  820734,  635726,  772407,  1046197, 940679,  880918,  752007,
    820844,  734595,  649956,  745372,  631239,  748349,  674645,  875113,
    718849,  665216,  786646,  644513,  706871,  702408,  761534,  765484,
    684138,  744222,  609888,  996345,  815584,  746626,  794971,  651713,
    774402,  749841,  670805,  610952,  704941,  704613,  631662,  578710,
    583349,  1020591, 857048,  812118,  728950,  765771,  762687,  682967,
    745274,  646474,  723543,  814406,  830916,  681501,  633605,  749672,
    669703,  578327,  726883,  651761,  1000351, 894569,  797526,  653126,
    778338,  671118,  706549,  650501,  1246094, 954427,  1107286, 1108326,
    908128,  1083197, 929980,  991132,  835852,  1165515, 932569,  834439,
    911806,  748445,  724914,  875325,  683986,  861095,  769403,  836115,
    1111585, 914583,  996877,  885617,  861277,  839696,  830347,  711274,
    647435,  652696,  1082526, 910900,  713056,  845168,  752103,  674758,
    774363,  770300,  633270,  688318,  694361,  1051543, 882701,  836394,
    750817,  677345,  794872,  787889,  774954,  744772,  1041246, 684285,
    808592,  664742,  611894,  667661,  766215,  740682,  607643,  671331,
    829697,  710167,  774415,  746021,  706956,  633555,  725993,  705176,
    703563,  811617,  770437,  761036,  682112,  731186,  647030,  991649,
    745239,  773615,  634597,  743565,  707433,  580239,  730221,  653257,
    704253,  681787,  794358,  654254,  614776,  665326,  708157,  632268,
    1642544, 1642902, 1400424, 1209842, 1315153, 1431231, 1247792, 1397331,
    1146833, 1629683, 1462415, 1371962, 1228383, 1279422, 1048736, 1143880,
    1166649, 1042850, 1162885, 951680,  960848,  1555640, 1309578, 1242379,
    1174623, 1167534, 1046787, 995640,  1137579, 1112705, 1249397, 1275646,
    1144956, 1215504, 1152652, 944512,  890443,  966759,  1088513, 1459875,
    962807,  1149052, 994901,  859560,  937673,  1054758, 1049316, 866568,
    1309767, 1006125, 1046573, 1019308, 1096158, 896546,  982861,  876039,
    1040858, 1086389, 890061,  1051011, 940454,  990851,  1018207, 836340,
    884563,  817384,  1423938, 1173686, 1194698, 937092,  878357,  1015849,
    1044849, 1017709, 1387258, 1248499, 953252,  997030,  972199,  1047134,
    1041064, 1042672, 934904,  887317,  1016006, 987087,  987622,  1165086,
    1083706, 889751,  1048608, 939525,  1018331, 836081,  994103,  1371142,
    1226777, 1276394, 1136005, 1226467, 1165206, 1040123, 1072125, 1162767,
    1168509, 1094354, 1096264, 958829,  850078,  1029423, 1031108, 921885,
    826770,  973717,  975711,  871698,  982409,  983069,  1041518, 1011337,
    831969,  807169,  882763,  978965,  878074,  763349,  952178,  783680,
    1045532, 958709,  1021204, 839766,  993795,  816971,  789238,  837204,
    745834,  913704,  909849,  750018,  789572,  745098,  876757,  783452,
    1029548, 1028406, 845819,  952565,  925093,  927262,  758997,  717754,
    900106,  871930,  1160868, 952230,  763832,  881292,  788893,  717677,
    831972,  679528,  678534,  749938,  958631,  954486,  788440,  858630,
    906870,  901782,  767518,  877170,  854147,  768691,  803950,  723570,
    790747,  788918,  857665,  830392,  832351,  955240,  716881,  831676,
    857454,  830161,  832033,  1562355, 1398025, 1023966, 1114369, 1172585,
    961139,  1047290, 1111038, 992553,  941344,  1114634, 994090,  997541,
    897656,  979561,  986597,  990973,  874617,  963797,  930277,  829574,
    935056,  1245217, 1046684, 970334,  792551,  930584,  763751,  887931,
    729128,  795823,  1209623, 1081742, 969159,  966347,  797455,  919294,
    910484,  814635,  863913,  772777,  891137,  733138,  864831,  1170839,
    982881,  983948,  933851,  839022,  886283,  889962,  687616,  775647,
    839754,  691671,  1166664, 959617,  908857,  912075,  745075,  834720,
    832440,  745250,  859814,  769381,  681982,  1111663, 997453,  932902,
    887965,  869131,  690800,  836064,  649825,  793204,  940510,  957207,
    789821,  859169,  770925,  836685,  747622,  811736,  725912,  672186,
    1111250, 1111719, 865593,  869070,  776429,  841726,  709102,  649540,
    995000,  928426,  764013,  868268,  772229,  837131,  683440,  704704,
    813268,  792975,  649978,  790139,  709828,  1273416, 1211602, 1087372,
    963973,  1028868, 1143495, 1108638, 1116036, 1083993, 1079856, 1035088,
    1070197, 960101,  866926,  956914,  908795,  841038,  908237,  911730,
    821574,  1216104, 1021774, 971786,  750960,  707995,  776964,  1181680,
    993878,  814019,  850913,  922395,  899456,  734239,  805234,  893074,
    801493,  711866,  844457,  1136011, 1023036, 959482,  746643,  702266,
    815108,  732261,  754655,  664149,  817800,  1137518, 909342,  819410,
    889798,  703826,  813718,  731585,  682074,  812213,  662894,  729044,
    735899,  1084124, 914543,  747018,  820174,  869409,  781453,  694278,
    822203,  672275,  716492,  1109634, 932141,  889753,  773684,  753481,
    836106,  682769,  649930,  713145,  815035,  794766,  651163,  973806,
    904461,  704175,  778509,  811582,  664028,  771145,  791873,  693759,
    771262,  906441,  868641,  843576,  691710,  819980,  769480,  630533,
    633527,  1105139, 1140617, 1145810, 1021156, 905652,  1045155, 984548,
    811179,  883627,  930703,  767033,  762523,  829724,  903617,  875920,
    989713,  986896,  815066,  912724,  882067,  791453,  839730,  692503,
    860823,  833845,  693051,  1140136, 1136336, 959799,  862976,  756252,
    734992,  865346,  820623,  676594,  734589,  816445,  1096411, 888491,
    795168,  775075,  686934,  711538,  818379,  787012,  648959,  717877,
    1097218, 927968,  926396,  833480,  706788,  835297,  749341,  783730,
    703629,  789482,  1040679, 857225,  881086,  816371,  709909,  788065,
    614571,  772415,  689892,  613016,  749866,  1068199, 862980,  770378,
    745148,  671116,  666604,  723208,  769071,  769156,  858171,  789885,
    792655,  793626,  652306,  710730,  770407,  635115,  746307,  616042,
    878468,  787245,  730083,  709355,  746926,  749141,  748236,  1164720,
    961945,  1100110, 1096729, 979713,  929751,  1044736, 1043069, 930657,
    934801,  1012020, 1031147, 848473,  877953,  929676,  832434,  921943,
    823371,  903944,  1171279, 932483,  768920,  878033,  722092,  686988,
    767092,  835567,  836909,  960787,  792108,  909260,  754235,  791715,
    855152,  813717,  815983,  811552,  1104446, 909926,  829020,  877215,
    714961,  688921,  747938,  788778,  794045,  906054,  983503,  877305,
    723685,  855293,  856727,  706216,  832274,  701988,  808674,  785294,
    782531,  646314,  1043455, 723195,  766719,  632119,  765106,  837849,
    669808,  800963,  716394,  787942,  634287,  1048355, 1043293, 935414,
    815011,  671396,  728393,  787649,  744802,  665883,  687359,  614045,
    667780,  875292,  833738,  816387,  785152,  743164,  663203,  630763,
    745763,  743963,  668355,  1139248, 1165731, 1164549, 956343,  888785,
    989515,  810749,  1020721, 990610,  814518,  954203,  1044679, 909940,
    748347,  873211,  830128,  678300,  834090,  996830,  766943,  795884,
    837469,  830690,  794161,  711048,  666719,  793638,  713364,  889334,
    909070,  816348,  820969,  820756,  813948,  796933,  770869,  688817,
    821899,  787690,  644437,  614493,  671594,  773139,  693035,  750794,
    619126,  834595,  683730,  748602,  788289,  783895,  703402,  745936,
    763160,  743960,  608984,  672937,  812772,  711733,  635616,  748335,
    745147,  725723,  597252,  706266,  710312,  582860,  913187,  854601,
    814604,  708484,  688988,  729596,  598534,  667745,  726107,  594908,
    727490,  726134,  893313,  792542,  777332,  615204,  609743,  726368,
    597575,  578884,  635950,  993768,  829081,  743939,  793020,  711505,
    771101,  749151,  612808,  727960,  651126,  580670,  1420177, 1194116,
    1071056, 1134490, 993191,  964121,  878065,  1012791, 832155,  834339,
    826395,  956032,  838608,  805719,  878617,  850764,  761414,  771388,
    1138442, 791050,  911946,  863423,  856608,  838663,  690656,  918361,
    994792,  933887,  891438,  716286,  774783,  691259,  797170,  795664,
    713939,  732096,  655376,  960133,  856680,  813725,  671719,  767312,
    764097,  682824,  769075,  1068421, 880710,  898314,  741180,  769194,
    685634,  666100,  727521,  763300,  629806,  782419,  787036,  705727,
    683836,  762146,  838054,  767761,  795904,  770612,  690465,  629939,
    726631,  728115,  726512,  653969,  723114,  651060,  744775,  741525,
    666475,  851316,  852772,  793430,  633066,  764937,  725066,  745253,
    669063,  646980,  594481,  839493,  764395,  628275,  728296,  596897,
    596169,  725712,  726779,  597123,  1168106, 972094,  862303,  1047284,
    886794,  992160,  978975,  878583,  791183,  878428,  681815,  701655,
    830756,  742863,  685725,  1116228, 839222,  863602,  707969,  773282,
    792401,  813733,  793048,  648217,  711863,  1086618, 749615,  872947,
    715762,  780367,  847270,  820734,  798947,  655180,  772407,  822090,
    649956,  710368,  789470,  706008,  748440,  1045947, 788715,  641139,
    743363,  609387,  665238,  741963,  996345,  892144,  832030,  712792,
    694713,  746464,  748373,  631662,  726294,  596721,  708924,  636607,
    838359,  857048,  851946,  812118,  728950,  652755,  632412,  687408,
    597898,  723241,  728350,  993699,  795206,  774531,  694683,  745924,
    706894,  578327,  728525,  707102,  1000947, 680999,  797526,  796136,
    778338,  747474,  667625,  726126,  594895,  707518,  1041977, 1108326,
    1044971, 1049519, 858690,  913688,  882152,  814530,  1163591, 957428,
    979864,  875619,  913055,  814932,  717850,  832720,  833395,  828913,
    836115,  753712,  996877,  766583,  727635,  795001,  864926,  770328,
    837249,  830347,  793943,  1087194, 909428,  748105,  866026,  821435,
    820680,  727914,  637314,  797839,  797829,  770300,  636938,  939723,
    787658,  733515,  794872,  790556,  751182,  679364,  1039538, 935014,
    873740,  831811,  785244,  779996,  745399,  667661,  740682,  815197,
    745750,  792463,  773123,  666993,  579491,  725993,  653769,  1018873,
    912855,  764861,  668615,  794103,  688608,  731186,  653110,  668812,
    729183,  654235,  790923,  649737,  710043,  691324,  747203,  615203,
    610734,  707433,  633712,  597823,  705333,  577804,  995913,  711686,
    635575,  743989,  727379,  652939,  708157,  632268,  1755692, 1642902,
    1524892, 1250842, 1364989, 1393792, 1140795, 1396686, 1256244, 1371558,
    1305781, 1071023, 1170192, 1227031, 1228495, 1165811, 1042850, 984149,
    1039285, 1168054, 1308730, 1208636, 992219,  1174623, 1167534, 934997,
    1108737, 992466,  1151885, 1147497, 937500,  1089627, 887774,  1169425,
    962807,  1049632, 1148145, 985267,  1080475, 1041782, 854129,  1049316,
    946520,  1196026, 1101975, 1046573, 1135189, 1104801, 982861,  876039,
    1039289, 1041880, 854251,  1246446, 910837,  890061,  971817,  992059,
    817384,  891826,  1276206, 991690,  1071827, 956408,  1015849, 1045183,
    834269,  1388142, 1163386, 1045966, 1109593, 997030,  1047134, 859037,
    941068,  1042672, 808378,  914641,  988757,  809900,  1394074, 912964,
    1090301, 970463,  939525,  989027,  1024541, 992434,  1370423, 1125003,
    1305509, 1136005, 1009549, 1226467, 1005391, 982073,  1162767, 1150887,
    942822,  1070692, 1034290, 1038627, 929491,  976663,  826770,  902751,
    975711,  871698,  1299405, 1299058, 1095573, 1040360, 854399,  1011337,
    1016584, 985719,  802294,  932030,  833992,  927680,  839002,  993795,
    966214,  962776,  789238,  909070,  745834,  810421,  816859,  1036076,
    1034384, 933685,  927964,  723554,  813784,  887965,  1001473, 1028406,
    923167,  979444,  853726,  927262,  831119,  805977,  874345,  718887,
    1161395, 1040204, 977129,  802357,  929779,  763832,  877781,  720357,
    874673,  784226,  743620,  827549,  678534,  900965,  858630,  768424,
    805005,  859078,  877170,  721376,  1164564, 1045212, 978821,  883108,
    790747,  878565,  832304,  768474,  680661,  831588,  684132,  1164405,
    974923,  766510,  877970,  719624,  875821,  716881,  782328,  743282,
    830161,  831165,  749432,  1308923, 1077081, 1172831, 1244831, 1182980,
    1114179, 1144629, 1149141, 1114634, 994090,  1305964, 1021514, 912435,
    803298,  830759,  860963,  928504,  762230,  931659,  767776,  1115015,
    990847,  991810,  814331,  863781,  763751,  887012,  887498,  889242,
    795823,  998594,  966347,  945503,  777404,  821371,  814635,  891825,
    796451,  866560,  712054,  1167387, 963798,  1048799, 918749,  754672,
    889962,  880300,  723192,  836087,  834806,  687616,  866696,  684171,
    839754,  754482,  1047680, 912075,  718049,  745250,  855783,  702642,
    744486,  932902,  838816,  841765,  753345,  650613,  672007,  793270,
    708317,  654413,  1144219, 1138743, 1019748, 859169,  750385,  731659,
    862645,  857781,  671769,  836635,  669155,  811517,  672186,  884931,
    795984,  776429,  838032,  834289,  747981,  790226,  710065,  1113589,
    885309,  794757,  711083,  839597,  831710,  790208,  649406,  729719,
    706833,  1515911, 1273416, 1143479, 963973,  1028868, 1137366, 1081214,
    881104,  1082184, 1271382, 871947,  1000252, 956914,  860049,  765279,
    813009,  1211590, 990919,  971786,  771824,  865911,  888334,  867364,
    866573,  994408,  894525,  947191,  922395,  844457,  690158,  759349,
    1136011, 959485,  746643,  866890,  859500,  702266,  813599,  664149,
    737158,  783023,  861300,  863833,  838698,  682074,  751746,  811940,
    665031,  886318,  977944,  914543,  710607,  850279,  738852,  816224,
    772497,  695524,  777367,  935750,  764019,  889753,  835343,  749521,
    666580,  793954,  791604,  648276,  708804,  792832,  1076048, 817508,
    628311,  693759,  768376,  908850,  850865,  823646,  812737,  769480,
    772790,  691945,  798968,  633097,  771845,  633527,  1014151, 1169899,
    963517,  1050377, 1104911, 1103813, 986635,  1072524, 858613,  934198,
    1221820, 1032558, 927256,  984548,  883627,  962179,  829724,  903617,
    812130,  783282,  1169250, 1165771, 961578,  939256,  796245,  726445,
    839408,  692503,  753435,  860823,  770907,  836856,  840400,  865346,
    711861,  841915,  816445,  814080,  728388,  768575,  752652,  833866,
    787012,  799924,  659672,  1097218, 904006,  833480,  857753,  861322,
    706788,  835297,  749341,  788170,  727370,  645810,  724715,  837390,
    839001,  820006,  789999,  650777,  788065,  649178,  746971,  613016,
    674551,  1071485, 907773,  770378,  815140,  806916,  789119,  788319,
    651297,  683008,  637916,  936618,  789885,  731311,  793626,  790030,
    616974,  691012,  613804,  746931,  936676,  723356,  691131,  730083,
    788969,  705410,  749141,  768694,  748554,  615399,  1205884, 1225940,
    1096729, 1044334, 883871,  1043069, 920422,  980450,  809611,  960885,
    792816,  858208,  876962,  808143,  875363,  881406,  725901,  911726,
    727969,  783972,  835275,  835567,  745192,  836573,  942672,  792108,
    856887,  816012,  734841,  865805,  864248,  818138,  692138,  725168,
    1095992, 925410,  727995,  863489,  771771,  786858,  794045,  653771,
    1095091, 874793,  856727,  829694,  824818,  679420,  701988,  645122,
    701295,  705773,  878662,  816515,  788895,  700863,  612125,  770405,
    632119,  748160,  616785,  886299,  691466,  807519,  663502,  763957,
    633382,  700947,  722298,  834836,  833142,  686723,  815635,  790877,
    784999,  744802,  665883,  612948,  742964,  790391,  705593,  783705,
    699028,  768058,  685984,  665099,  1109891, 909020,  939335,  1041025,
    989515,  1020721, 991532,  990458,  890382,  1163803, 913619,  879991,
    722670,  877086,  853545,  827679,  830741,  678300,  750352,  838778,
    795884,  707896,  792517,  810609,  814241,  728841,  1084843, 889334,
    969718,  711877,  694141,  734928,  816181,  772552,  693421,  880913,
    734329,  794190,  651058,  787690,  644437,  771248,  633485,  666531,
    677701,  856268,  877646,  834595,  708841,  703402,  611602,  767532,
    666604,  745772,  991625,  746684,  775938,  693736,  748335,  671658,
    706985,  652041,  704954,  577570,  710312,  1018826, 813028,  668390,
    632597,  764074,  625310,  652985,  744645,  814211,  830358,  682386,
    748724,  713508,  773414,  748452,  706306,  578827,  597575,  633495,
    993768,  743939,  775190,  608600,  705856,  580670,  981517,  1070804,
    1066706, 878065,  957828,  832155,  1014001, 1002539, 901232,  956032,
    858990,  771947,  907230,  747304,  813821,  854656,  761414,  939928,
    911259,  730293,  854794,  732055,  751483,  669441,  814469,  669365,
    1109574, 994792,  771672,  774783,  840220,  837182,  795664,  794723,
    654076,  708676,  884535,  742857,  809102,  840645,  813725,  722823,
    770606,  635800,  1068421, 880710,  898932,  854870,  704492,  835829,
    811624,  765255,  686890,  762968,  762146,  690023,  912674,  814727,
    730771,  712717,  767447,  629939,  686676,  724783,  653969,  1043587,
    878992,  875080,  723114,  670049,  790308,  787877,  630798,  682805,
    745185,  614372,  836737,  911567,  765712,  652536,  770399,  628108,
    650497,  723555,  1020948, 851990,  700423,  799016,  710566,  631778,
    764395,  728296,  650630,  615551,  727613,  958285,  1112144, 997380,
    941305,  1022784, 912032,  993927,  1048393, 878583,  933624,  913955,
    717608,  830080,  766849,  679440,  833684,  685725,  889079,  773282,
    687318,  747850,  811095,  793048,  711863,  914376,  909479,  695710,
    825297,  816913,  798947,  772511,  636628,  860001,  940679,  878754,
    674439,  710368,  745372,  772617,  690928,  746668,  610306,  753236,
    616977,  832734,  683588,  812940,  727132,  786646,  742478,  761534,
    664377,  741963,  832030,  746626,  794162,  613809,  670805,  704941,
    730607,  596721,  652074,  794707,  793673,  765771,  626565,  730144,
    597898,  665701,  728716,  595627,  650243,  892921,  681501,  795206,
    792999,  613989,  610160,  669703,  633356,  726883,  706229,  633021,
    816947,  613172,  747474,  730681,  632991,  708982,  1390038, 1246094,
    1041977, 1079343, 1083197, 886451,  1049519, 852144,  886429,  986679,
    1163591, 1044784, 802233,  931976,  932569,  814932,  717850,  745519,
    856261,  704852,  835391,  753712,  1111585, 914583,  932418,  885998,
    830608,  792607,  668521,  730062,  652696,  893605,  845660,  845168,
    752103,  774363,  637314,  694399,  774444,  772957,  939723,  882701,
    724598,  750817,  821747,  790556,  705052,  749369,  637258,  746307,
    679364,  831514,  745823,  808592,  664742,  646261,  706162,  699558,
    610966,  991429,  833695,  650376,  774415,  692847,  706956,  579491,
    633555,  703167,  583400,  857964,  668615,  705244,  770437,  633740,
    627186,  723570,  595360,  647030,  992550,  816069,  829304,  791790,
    771789,  750264,  744262,  725563,  597823,  705253,  742816,  794358,
    654254,  635575,  689985,  751494,  611367,  708679,  708107,  638368,
    1563949, 1563816, 1529744, 1209842, 1468076, 1470744, 1247971, 1175152,
    1140795, 1396686, 1634767, 1371558, 1228383, 1305781, 1170192, 1278700,
    1013740, 1228495, 1097475, 984149,  1277733, 1242557, 1018538, 1208636,
    1110333, 1112092, 1142186, 908093,  1111790, 1278467, 1218537, 1089368,
    1187363, 1152652, 1023572, 1086565, 916178,  1082150, 887774,  1233340,
    1009608, 1169425, 1110345, 985267,  1047998, 866568,  1455379, 1224501,
    955272,  1019308, 1104801, 991472,  1094988, 1039673, 851151,  1041880,
    1040858, 940897,  910837,  860517,  1044633, 1018207, 990450,  1173686,
    1136540, 1080441, 1066492, 838041,  1044849, 858384,  907580,  1107845,
    1085218, 972199,  941068,  852501,  808378,  1021077, 988298,  987622,
    1247473, 1113547, 998058,  1041418, 853579,  885389,  1018331, 886658,
    992434,  1631654, 1271738, 1235095, 1009549, 1097551, 1163050, 1195445,
    1224040, 1070692, 1073235, 880584,  1029423, 844605,  876227,  982409,
    808448,  885090,  1299058, 900877,  934919,  904950,  981211,  802294,
    932030,  927742,  761463,  1045532, 913898,  966214,  964985,  792749,
    862792,  913901,  906109,  1007834, 1034384, 927755,  986298,  810200,
    965054,  793918,  862643,  836838,  881233,  909361,  813784,  876757,
    717770,  1218194, 1029548, 845819,  979444,  853726,  921260,  875102,
    735888,  872981,  874345,  789402,  952230,  979430,  908684,  747325,
    720357,  784226,  858447,  766474,  831267,  834705,  1004002, 900965,
    958631,  810234,  705296,  767518,  700263,  706968,  1161922, 803950,
    765676,  838757,  816232,  878703,  788918,  746867,  854619,  831588,
    749615,  955240,  976131,  837182,  877970,  787683,  852363,  857454,
    700027,  832033,  1398025, 1248198, 1023966, 1172585, 961139,  913582,
    992553,  1115353, 1302531, 1042253, 857144,  812328,  979934,  929279,
    789217,  928504,  930277,  829574,  1244760, 991810,  792551,  842707,
    932166,  834864,  729244,  792386,  887228,  1213844, 1016018, 969159,
    867539,  863913,  772777,  796451,  710661,  866560,  918749,  880917,
    723192,  745068,  1169786, 982649,  806403,  835886,  882169,  885051,
    877270,  834720,  684146,  855783,  769381,  832721,  997453,  730300,
    868119,  777984,  650613,  819960,  796164,  654413,  1019748, 961780,
    914243,  750385,  888712,  710465,  704101,  729594,  811736,  914210,
    930931,  763935,  710418,  747981,  790763,  732667,  792390,  709218,
    1113589, 1112273, 831212,  711083,  831007,  683440,  788932,  649406,
    817810,  792733,  709828,  1515911, 1039511, 935917,  1137366, 969177,
    907670,  884535,  969989,  1082184, 1269384, 1070197, 871947,  914285,
    788243,  866926,  908795,  935521,  940562,  813009,  746148,  1211590,
    943103,  949613,  846875,  709430,  779648,  799879,  866406,  783220,
    1062798, 946930,  774211,  893074,  801493,  711866,  846033,  1137064,
    928459,  959485,  861063,  731855,  866890,  863632,  754655,  1137518,
    927684,  743140,  775046,  855867,  731585,  811940,  813205,  665031,
    977944,  911443,  747018,  869409,  781453,  850279,  761836,  820568,
    668024,  775777,  775875,  699264,  764019,  837420,  865731,  749521,
    815035,  666580,  791604,  794766,  908916,  817303,  840921,  734714,
    664028,  767910,  770489,  630212,  768376,  628197,  694415,  742115,
    868641,  709484,  758540,  812737,  730533,  633097,  774885,  1456227,
    1230024, 1231607, 939400,  993580,  986635,  1045139, 1047275, 1221820,
    983519,  964233,  861804,  925975,  880234,  726049,  874409,  882342,
    815066,  883094,  753435,  708995,  687970,  840400,  963665,  862976,
    915623,  892595,  715332,  820623,  676594,  841915,  694732,  1103492,
    1096411, 987189,  930575,  834976,  888491,  716593,  839620,  752652,
    711538,  795462,  659672,  717877,  1094740, 765123,  882236,  769231,
    832592,  685760,  744719,  788170,  666928,  785506,  783730,  1040232,
    724715,  839001,  751977,  816371,  650777,  614571,  772415,  689892,
    956694,  902540,  862980,  709972,  810733,  636923,  788319,  705037,
    631228,  690115,  752934,  819847,  790030,  671376,  635115,  746175,
    860786,  723356,  787245,  790218,  709355,  705410,  772620,  689680,
    748554,  1467545, 1306271, 1167895, 989196,  1100110, 903916,  1044334,
    1075514, 961116,  1223708, 1095604, 848473,  809611,  766075,  873712,
    903944,  1171279, 964497,  983714,  811620,  880261,  836645,  885783,
    792168,  783972,  836909,  955465,  891057,  888173,  734841,  791715,
    864248,  862211,  838266,  815983,  726987,  928238,  771771,  835578,
    684776,  703662,  646581,  1101363, 925283,  786194,  829694,  683597,
    722509,  701295,  1043455, 934029,  785544,  833250,  816515,  816582,
    730274,  745027,  743647,  612125,  770405,  745276,  748160,  616785,
    905072,  744400,  858665,  835031,  763957,  630138,  762852,  684047,
    862472,  875524,  722298,  784809,  833142,  747602,  671396,  791148,
    707461,  768036,  665826,  614045,  1050622, 1046114, 836457,  689062,
    814154,  816387,  705593,  612565,  612471,  615538,  1388563, 1244219,
    967145,  1047911, 1043416, 990509,  811800,  990458,  890382,  1164401,
    979100,  932242,  909940,  790345,  682064,  853545,  767983,  684654,
    911069,  996830,  707896,  772324,  752876,  794161,  649784,  711048,
    713364,  911216,  846110,  728692,  693931,  654421,  770869,  772504,
    1050188, 722595,  822074,  675342,  794314,  788716,  614493,  773139,
    633485,  693035,  666531,  1045745, 1043439, 937486,  789179,  683730,
    812256,  816336,  790705,  668413,  745772,  611520,  672937,  832126,
    711733,  775938,  667118,  706985,  725723,  704954,  577570,  1019804,
    856960,  854601,  793310,  652082,  632597,  598534,  745755,  667745,
    725342,  814211,  893313,  833082,  792542,  649025,  752184,  609743,
    731137,  706936,  707587,  579303,  889877,  829102,  793749,  793020,
    711505,  747452,  742240,  608600,  705845,  706786,  631548,  705856,
    635730,  912563,  1070804, 883119,  957828,  1046698, 858063,  906421,
    834339,  984999,  901232,  935878,  838608,  907230,  813821,  856156,
    883690,  789937,  855271,  855920,  1138271, 911259,  911946,  860349,
    854794,  768284,  732055,  834168,  812809,  669441,  1114664, 798590,
    869164,  695826,  755025,  656873,  818883,  792667,  708676,  655376,
    901824,  708472,  665385,  633869,  629295,  769075,  1066129, 704492,
    769194,  661652,  722720,  782419,  627700,  763092,  1016791, 654143,
    767750,  690465,  767447,  596663,  670679,  648511,  599805,  929992,
    875080,  784160,  688462,  813349,  670049,  784151,  765009,  744775,
    612316,  745185,  742665,  1014512, 911567,  730053,  710970,  633066,
    764937,  685640,  723555,  650677,  1020249, 700423,  817069,  772705,
    631778,  751541,  615551,  725712,  1167554, 913456,  1085347, 1052422,
    941305,  855668,  991556,  813362,  1022784, 889147,  1048393, 977879,
    837085,  723050,  877083,  878428,  744837,  853648,  742863,  833684,
    749836,  913104,  933998,  766774,  796952,  863602,  707969,  839993,
    811095,  973602,  909479,  872947,  695710,  773754,  636689,  695411,
    713006,  778607,  772407,  1046197, 880918,  720560,  687829,  734595,
    794487,  790447,  789470,  631239,  746668,  875762,  665216,  788715,
    706871,  609387,  765484,  684138,  995406,  996345,  833757,  774402,
    610952,  704941,  652074,  578710,  708924,  636607,  857048,  669334,
    793673,  771815,  626565,  723367,  745274,  595627,  646474,  774359,
    633021,  578332,  1000351, 816947,  894569,  832061,  797526,  634921,
    751339,  705752,  578580,  650501,  708982,  581068,  1246094, 1162393,
    1107286, 1108326, 991227,  1038532, 1039990, 991132,  886429,  835852,
    987738,  991164,  957428,  979864,  875619,  932569,  880940,  790502,
    783311,  683986,  829236,  687944,  914583,  996877,  836341,  885617,
    864926,  770328,  839696,  794647,  815517,  789458,  845168,  821435,
    816105,  670129,  727914,  694399,  655213,  633270,  772957,  694361,
    864592,  724598,  787658,  794279,  794872,  654152,  787889,  617106,
    773100,  774954,  622175,  935014,  875054,  724439,  641271,  744230,
    611894,  740682,  829697,  682920,  790290,  650376,  710167,  742215,
    666993,  706956,  633555,  725993,  707221,  637404,  839396,  811617,
    727645,  769495,  633740,  761036,  746457,  668812,  729183,  599906,
    891145,  773615,  707433,  653257,  577804,  794358,  711686,  743659,
    611367,  727379,  707045,  638368,  1642902, 1346537, 1400424, 1250842,
    1475531, 1175152, 1396317, 1247792, 1397331, 1634767, 1629683, 1339119,
    1071023, 1279422, 1143880, 1108716, 1166649, 956068,  1042850, 1396097,
    1074596, 1242379, 1166069, 956771,  1046787, 1137579, 992466,  1112705,
    1048540, 1187614, 972576,  1151885, 1142701, 1118208, 1082150, 890919,
    1229174, 962807,  1110346, 994901,  903402,  1049316, 866568,  1309767,
    1165988, 955272,  1019308, 932147,  1392479, 1140912, 1167357, 957363,
    1111102, 1086389, 890061,  860517,  940454,  934321,  990851,  913405,
    884563,  1423938, 1072284, 937092,  1111570, 913628,  878357,  1021978,
    1015849, 1044849, 934487,  1015259, 1161785, 1107845, 934904,  887317,
    808577,  886115,  889847,  1393261, 1164952, 953901,  1042544, 1113547,
    889751,  1052792, 1044755, 989027,  1631654, 1336465, 1070709, 1271738,
    1235095, 1226467, 1005391, 1168509, 1049210, 1094354, 982801,  1034290,
    1029423, 1031108, 876227,  1095827, 1041518, 1011337, 978965,  929011,
    927742,  931074,  765425,  995256,  993795,  886258,  964985,  789238,
    911340,  837204,  909070,  1222681, 1099933, 848864,  932680,  879694,
    789572,  908328,  876091,  717770,  883952,  1001473, 1029548, 923167,
    927262,  758997,  921236,  826010,  874794,  871930,  1161395, 1040204,
    979430,  763832,  908684,  747325,  881292,  874673,  717677,  679528,
    858447,  827549,  678534,  1190536, 828767,  954486,  858630,  901782,
    739175,  854338,  978821,  880055,  747991,  883108,  831673,  854619,
    768474,  1042315, 766510,  911473,  787683,  828428,  680017,  765251,
    830161,  680095,  832033,  1562355, 1310826, 1077081, 1086870, 970439,
    1171496, 961139,  1144629, 1115353, 997541,  979561,  932976,  1021514,
    839076,  986597,  990973,  958741,  829574,  935056,  1244760, 1023707,
    1046684, 937831,  970334,  914587,  729128,  795823,  1209623, 1019114,
    966347,  797455,  756000,  913037,  863631,  1170839, 807968,  933851,
    787601,  687616,  866696,  711079,  833904,  691671,  1169786, 959617,
    912075,  813606,  792335,  832440,  833643,  834841,  684023,  1111663,
    767286,  730300,  869131,  777984,  836064,  748338,  793270,  649825,
    1144219, 907599,  889505,  862645,  853250,  817779,  836635,  816999,
    1111250, 836630,  727436,  832606,  790763,  709102,  817470,  649413,
    1112273, 887048,  729938,  794757,  772229,  704704,  813268,  792733,
    792975,  649978,  706833,  1087372, 1178638, 1025026, 881104,  1116036,
    998756,  884280,  1271382, 1070197, 830934,  996705,  866926,  841038,
    746148,  821574,  1021774, 918289,  750960,  727701,  866406,  783220,
    993878,  994408,  814019,  922395,  753676,  734239,  893074,  845594,
    691426,  711866,  756253,  844457,  690158,  1023036, 861063,  913399,
    800523,  868517,  814816,  668066,  843270,  664149,  817800,  737158,
    909342,  743140,  889798,  861300,  772356,  682074,  662894,  729044,
    735899,  1084124, 886318,  911443,  747018,  781453,  672275,  738852,
    735121,  632389,  796607,  694939,  777367,  637417,  1109634, 995034,
    837420,  726149,  708661,  840725,  794921,  815035,  793954,  792832,
    712428,  1082667, 973806,  866177,  757911,  817154,  817508,  664028,
    771145,  1082225, 885174,  908850,  779503,  734981,  649523,  633527,
    1199076, 1231607, 1105139, 1145810, 939400,  1046196, 861992,  1042978,
    1047275, 1096984, 984548,  925975,  927741,  762523,  903617,  719778,
    783282,  815066,  937781,  912724,  751117,  859888,  770907,  833845,
    1140136, 1136336, 862976,  756252,  893625,  841330,  816445,  734839,
    1096411, 868675,  775075,  836425,  833866,  787012,  703657,  717877,
    926396,  830244,  651099,  666928,  727370,  789482,  1040232, 933866,
    881086,  837390,  689753,  820006,  745274,  747333,  614571,  689892,
    749866,  956694,  747736,  671116,  769071,  769156,  764924,  768839,
    879795,  724093,  710730,  790308,  770407,  635115,  691012,  749009,
    1045184, 787245,  838487,  691131,  672381,  786888,  669350,  618866,
    1459996, 1229194, 961945,  1045132, 1140391, 1096729, 1041029, 1074614,
    930657,  934801,  1229167, 1031147, 920422,  977991,  877953,  929676,
    766075,  721905,  903944,  905906,  808143,  874281,  1168539, 983714,
    812165,  722092,  686988,  745676,  686640,  836573,  1015847, 909260,
    754235,  855152,  709503,  840658,  815983,  811552,  909926,  925410,
    829020,  877215,  714961,  688921,  747938,  727791,  653771,  828691,
    877305,  706216,  765842,  832274,  825689,  679420,  783813,  722509,
    784473,  645122,  705773,  934029,  723195,  748409,  816582,  649743,
    784702,  646481,  632119,  612088,  669865,  1076436, 886299,  897570,
    744400,  804077,  765106,  837849,  770243,  648596,  680242,  935414,
    686723,  815011,  671396,  728393,  791148,  787649,  613189,  746289,
    667780,  836457,  689062,  748509,  785152,  644284,  743164,  747629,
    745763,  743963,  992652,  888785,  1047911, 860196,  810749,  1017642,
    990610,  883483,  1163803, 954203,  1044679, 748347,  830128,  743919,
    859188,  767983,  834090,  886525,  772324,  810609,  793638,  1084843,
    694141,  820756,  673375,  728692,  775232,  796933,  654421,  770869,
    1044439, 879295,  822074,  712829,  644437,  748265,  614493,  753735,
    677701,  937486,  834595,  748602,  816336,  788289,  785434,  668413,
    763160,  608984,  745611,  991625,  682711,  711733,  748335,  745147,
    706266,  582860,  1019804, 854601,  814604,  795301,  708484,  688988,
    764074,  727215,  727490,  598286,  893313,  792542,  748349,  745660,
    748452,  708123,  597575,  708301,  633495,  743939,  793020,  771101,
    749151,  612808,  670378,  665055,  727960,  595430,  1420177, 1134490,
    1112169, 1076498, 964121,  878065,  1012791, 1046698, 936000,  1191660,
    956273,  858990,  838608,  904208,  900769,  740403,  767222,  850764,
    700950,  761414,  959135,  959901,  791050,  862522,  886174,  709934,
    814503,  834168,  838663,  727252,  918361,  774783,  843713,  755025,
    713939,  796172,  712926,  960133,  902377,  858716,  708472,  770444,
    841971,  671719,  808729,  653672,  764312,  682824,  769075,  693856,
    898314,  854996,  831557,  685634,  666100,  722720,  629806,  647064,
    705727,  683836,  1016791, 838054,  767761,  794573,  764409,  670679,
    653969,  929992,  831841,  812445,  790308,  784151,  645597,  699581,
    744892,  630798,  741525,  662653,  1015701, 836737,  765712,  730053,
    770399,  764937,  596249,  723739,  723355,  1020249, 671892,  794678,
    799016,  710566,  772705,  628275,  725966,  596897,  669607,  596169,
    726779,  1112144, 1051930, 1047284, 936137,  1018826, 813369,  889147,
    977879,  978975,  881667,  723050,  831810,  853648,  913104,  999922,
    933222,  839222,  727985,  773282,  792401,  727828,  793048,  914376,
    780367,  820734,  798947,  690572,  693972,  674439,  793433,  649956,
    710368,  772617,  631239,  744872,  666123,  753236,  1045947, 856542,
    834339,  811608,  727132,  788715,  609387,  743251,  609888,  832030,
    776693,  694713,  668345,  631662,  707712,  578710,  636607,  857048,
    851946,  728950,  652755,  767785,  687408,  597898,  745274,  611665,
    728350,  830916,  747918,  795206,  703653,  651761,  707875,  707102,
    578332,  633590,  1000947, 894569,  680999,  653126,  613172,  705752,
    707518,  1391045, 1162393, 1041977, 991227,  1079343, 989653,  811969,
    1023174, 1044784, 875619,  766691,  883457,  790502,  875733,  833395,
    836115,  835391,  687944,  1110548, 885617,  864926,  770328,  688885,
    682065,  745593,  794647,  909428,  748105,  694107,  821435,  797839,
    711919,  770300,  688318,  1051543, 1044469, 690227,  822963,  733515,
    648733,  749369,  617106,  774954,  746307,  755089,  752412,  622175,
    679364,  724439,  641271,  742586,  792463,  743564,  706670,  598542,
    708156,  583400,  912855,  651788,  705244,  731186,  728732,  599377,
    668812,  891145,  790923,  649737,  710043,  773615,  615203,  610734,
    667528,  597823,  635214,  829499,  711686,  772616,  747677,  665326,
    708679,  583687,  1961753, 1958462, 1755692, 1472637, 1364989, 1468076,
    1393926, 1141975, 1286779, 1256244, 1371558, 1123513, 1306580, 1305781,
    1143880, 1234952, 1004707, 1165811, 984149,  1162885, 1163577, 1051687,
    1557468, 1277733, 1242379, 1115649, 992219,  1174623, 1055061, 1137579,
    992466,  912676,  1359505, 1275646, 1218537, 998060,  1147497, 1118208,
    999300,  1084424, 1084229, 1169425, 1049632, 1026017, 1103734, 903402,
    985267,  1043655, 854129,  931429,  1459995, 1196026, 1046573, 931224,
    991472,  1066650, 1072018, 1039289, 932147,  1140912, 1045675, 1112334,
    910837,  971817,  854968,  988527,  809913,  809900,  1276206, 985323,
    1019901, 1066492, 912485,  1013983, 1015259, 1109593, 1047134, 1050723,
    941068,  1042672, 808378,  834506,  914641,  988298,  1393261, 1164952,
    1042544, 1113140, 889751,  939525,  1041418, 853579,  885389,  913740,
    992388,  993375,  815044,  892403,  1370423, 1305509, 1136005, 1097551,
    1040123, 1162767, 1038740, 1030363, 982801,  1038627, 850078,  1031108,
    976663,  802073,  1005432, 982702,  1164857, 1016584, 831969,  882763,
    802294,  929011,  932030,  761463,  933328,  881245,  839766,  913898,
    993795,  886258,  966214,  792749,  957905,  859075,  911340,  745834,
    810421,  816859,  1036076, 1034384, 927755,  884570,  793918,  933685,
    927964,  908328,  909361,  813784,  876091,  1218194, 803293,  782817,
    831119,  921260,  875102,  783532,  874345,  718887,  912112,  720357,
    831972,  853199,  832969,  749938,  981798,  1009105, 1004002, 900965,
    906870,  859078,  721376,  760472,  956424,  1045212, 932707,  747991,
    883108,  790747,  831673,  682459,  768474,  829852,  680661,  749615,
    1042315, 800287,  911473,  877970,  719624,  831676,  852363,  831165,
    680095,  831991,  749432,  1172831, 1219037, 1182980, 970439,  1171496,
    1149141, 941344,  994090,  1116412, 1305964, 1302531, 1168086, 912435,
    931633,  765311,  830759,  963797,  1045383, 990847,  991810,  814331,
    889510,  930584,  932166,  794326,  908664,  749008,  727266,  998594,
    1016018, 777404,  919294,  910484,  711476,  796451,  863631,  935096,
    916866,  836087,  687616,  748805,  833069,  838146,  691671,  1166664,
    912075,  723816,  877186,  785518,  702642,  934439,  767286,  887068,
    841765,  690800,  753345,  793152,  815443,  819960,  732897,  708317,
    1144219, 940510,  859169,  750385,  888712,  792648,  811977,  671769,
    672186,  763935,  886127,  747981,  709102,  812886,  792390,  709218,
    790575,  1113589, 915586,  928426,  885309,  865251,  711083,  749940,
    831710,  743287,  817810,  669552,  652298,  1360770, 1273416, 1143479,
    963973,  1059207, 1150498, 1077516, 1081214, 998756,  1079856, 1018388,
    830934,  1000252, 965349,  908237,  813009,  771824,  922636,  821215,
    727701,  866573,  1182369, 1062798, 774211,  922395,  892832,  845594,
    846506,  760356,  780390,  691292,  783367,  913399,  894882,  863632,
    771997,  840640,  687715,  813075,  783023,  909985,  819410,  703826,
    860255,  811906,  832843,  812126,  729044,  665031,  886318,  977944,
    914543,  694278,  823932,  816224,  800766,  716492,  775777,  775875,
    699264,  995034,  889753,  726149,  836106,  682769,  814035,  791604,
    817303,  866177,  668745,  734714,  732703,  628311,  647594,  774421,
    628197,  885174,  758540,  823646,  812737,  769480,  798968,  697516,
    1014151, 1169899, 963517,  910644,  1100018, 1072524, 884920,  1048591,
    942556,  1221820, 962179,  933503,  836161,  829724,  879974,  726049,
    746778,  783282,  729098,  1169250, 1165771, 1047044, 886913,  912724,
    726445,  770907,  687970,  840400,  693051,  963665,  794500,  915623,
    862031,  711861,  818322,  694732,  816445,  814080,  934146,  930575,
    834976,  840511,  752652,  833866,  818379,  703657,  904006,  985600,
    882236,  726947,  857753,  829889,  788762,  651099,  810821,  645810,
    651397,  933866,  879164,  839001,  789494,  613016,  674551,  881931,
    902540,  747736,  810236,  770378,  839719,  671116,  723208,  772481,
    789119,  705037,  637916,  838718,  689370,  817766,  793626,  648709,
    748998,  671376,  771708,  613804,  749009,  616042,  1046118, 840476,
    753720,  821758,  790218,  705410,  1229194, 1225940, 1011783, 1045132,
    938652,  1105030, 961116,  1043069, 1095604, 959719,  832434,  876962,
    721905,  780843,  875363,  876559,  1045821, 985513,  811620,  931687,
    768920,  812165,  876953,  745676,  705610,  745192,  942672,  909260,
    816012,  734841,  713151,  855152,  672314,  692138,  725168,  817337,
    1104446, 1095992, 909926,  865940,  714961,  727791,  1095091, 925283,
    877305,  723685,  856727,  765842,  829694,  824818,  679420,  806059,
    663754,  782473,  877172,  723195,  785544,  748409,  788895,  784576,
    700863,  687610,  745523,  665099,  1068761, 886299,  955382,  858665,
    837849,  810438,  633382,  785869,  767652,  630138,  762852,  634287,
    834836,  815635,  784999,  665883,  745178,  872662,  814154,  670713,
    789409,  612565,  685984,  745763,  665099,  747539,  615538,  1390741,
    1388563, 1081254, 967145,  911982,  990509,  991532,  890382,  1163803,
    932242,  834996,  722670,  715492,  782858,  832080,  911069,  933555,
    861777,  840082,  752876,  833024,  746084,  792517,  790426,  707634,
    1081469, 846110,  820756,  634872,  693931,  711916,  633579,  1044439,
    838503,  837042,  794190,  748265,  771248,  746171,  611003,  750794,
    856268,  877646,  789179,  667041,  788289,  790705,  745050,  687591,
    611520,  991673,  812772,  773792,  671658,  743512,  577979,  729016,
    652041,  582860,  703896,  795301,  763003,  625310,  744645,  612250,
    726107,  992852,  748724,  713508,  773414,  635166,  615204,  726368,
    731137,  708301,  814762,  829081,  743939,  749151,  670378,  705433,
    705845,  707226,  1420177, 981517,  1136176, 1019504, 1070804, 883119,
    909103,  1012208, 1014001, 1193191, 771947,  904208,  900769,  706231,
    878617,  855271,  1138442, 959901,  730293,  793998,  863423,  773348,
    814503,  817345,  672142,  732055,  751483,  811813,  771672,  889853,
    774783,  695826,  840220,  750584,  713939,  675612,  792667,  742857,
    809102,  840645,  671719,  791548,  653672,  709758,  682824,  770606,
    960213,  898932,  854870,  704492,  811624,  727521,  803320,  661652,
    765255,  686890,  787036,  627700,  762146,  853506,  703150,  813822,
    767750,  632377,  686676,  724783,  596168,  648511,  653969,  878992,
    875080,  784160,  831841,  813349,  787877,  651060,  748754,  765009,
    741525,  614372,  1015701, 852772,  710970,  688921,  725318,  596249,
    722817,  650677,  732336,  799016,  764395,  650630,  615551,  728392,
    653215,  1145413, 958285,  1085347, 1051930, 941305,  936137,  912032,
    1170202, 933624,  749518,  818960,  717608,  830080,  681815,  858984,
    766849,  836394,  833684,  1115256, 796952,  866909,  839136,  747850,
    665732,  790908,  1092951, 893995,  914376,  749615,  825297,  674772,
    636689,  1053392, 687829,  674439,  734595,  613333,  690928,  610306,
    616977,  937838,  875762,  718849,  727132,  786646,  784973,  665238,
    761534,  624704,  742344,  741963,  815584,  794162,  749841,  670805,
    748373,  710820,  583349,  838359,  851946,  817691,  652755,  665701,
    728716,  595627,  728350,  598737,  993699,  892921,  792999,  694683,
    746787,  610160,  596602,  578598,  633021,  704293,  1000351, 745433,
    714536,  750839,  594895,  650501,  632991,  1079343, 964691,  1049519,
    991132,  808904,  1163591, 978346,  913055,  814932,  724914,  875733,
    875325,  783311,  828913,  679137,  835391,  1111585, 795001,  861277,
    837249,  745593,  815517,  730062,  789417,  1087194, 970165,  814213,
    845168,  694107,  732952,  670129,  637314,  711919,  772957,  636938,
    694361,  882701,  836394,  690227,  821747,  790556,  746307,  752412,
    808592,  664742,  706162,  699558,  744230,  685999,  663609,  991162,
    890476,  833695,  790290,  650376,  773123,  774415,  611105,  633555,
    577424,  708156,  707221,  583400,  637404,  627186,  653110,  614389,
    992550,  829304,  832342,  681640,  791790,  710043,  747203,  750264,
    615203,  707291,  580239,  730221,  630863,  995913,  995959,  819845,
    689985,  751494,  581765,  731771,  652939,  580807,  583687,  638368,
    1563949, 1364989, 1468076, 1431231, 1175152, 1339119, 1371558, 1234952,
    1013740, 1108716, 1228495, 956068,  1204287, 984149,  1171022, 1277733,
    1396097, 1242557, 1208636, 1213861, 1082261, 1166069, 1112092, 1142186,
    1022752, 908093,  1359505, 1048540, 1089368, 1152652, 944512,  1086565,
    973174,  887774,  1204532, 1049632, 911946,  994901,  1080475, 1081412,
    931429,  1054758, 1224501, 955272,  931224,  896546,  853066,  940897,
    1388751, 1167357, 1112334, 910837,  995874,  1044633, 854968,  886087,
    1018207, 836340,  990417,  990450,  809900,  1430093, 1194698, 913628,
    887109,  965434,  1021978, 858384,  934487,  1013983, 907580,  1387258,
    1248499, 1045966, 1081794, 1085218, 941068,  988181,  809900,  1247473,
    1165086, 953901,  1113547, 998058,  1090301, 1044755, 990915,  886658,
    1631654, 1371142, 1125003, 1226777, 1305509, 1271738, 1228960, 1235095,
    1009549, 1104050, 1195445, 982073,  1164257, 960791,  1365813, 1030363,
    1070692, 844605,  978793,  1012035, 973717,  808448,  885090,  1299058,
    1041518, 1016584, 904950,  927680,  927742,  933328,  839002,  1045532,
    995256,  964985,  862792,  957905,  859075,  937407,  935583,  1229830,
    1099933, 986298,  862643,  760520,  879694,  1094937, 845819,  803293,
    955813,  758997,  921260,  921236,  826010,  875102,  783532,  977129,
    876208,  835549,  747325,  720357,  788893,  679528,  853199,  701455,
    741068,  1195821, 1190536, 981798,  788440,  768424,  810234,  859078,
    767518,  876706,  768691,  803950,  816232,  723570,  878703,  746867,
    830392,  749615,  1164064, 873829,  837182,  906326,  745186,  881308,
    875821,  680017,  852363,  857454,  1562355, 1285515, 1398025, 1308923,
    1248198, 1219037, 1000480, 1086870, 1172585, 913582,  1149141, 932976,
    912435,  986597,  979934,  929279,  958741,  930277,  829574,  931659,
    1023707, 860219,  937831,  991810,  963964,  792551,  938208,  887931,
    729244,  816973,  1213844, 998594,  841589,  821371,  913037,  867539,
    891825,  710661,  862970,  935096,  723192,  834806,  748805,  862053,
    833904,  684171,  838146,  754482,  959617,  835886,  908857,  792335,
    785518,  834720,  684146,  855783,  834841,  1114052, 997453,  934439,
    836806,  869131,  834624,  686278,  712182,  914243,  907599,  750385,
    815645,  704101,  765234,  811977,  815205,  669155,  811517,  728526,
    928845,  930931,  710418,  689892,  792390,  709218,  791218,  1112273,
    928883,  772229,  788932,  792733,  652298,  1515911, 1360770, 1211602,
    935917,  1025026, 1081214, 1108638, 907670,  969989,  1082184, 1269384,
    871947,  815124,  765279,  1216104, 990919,  918893,  969971,  792288,
    943103,  949613,  922636,  745471,  709430,  779648,  893318,  783220,
    993878,  826011,  898999,  729114,  844950,  756253,  759349,  1137064,
    928459,  783367,  911627,  893242,  731855,  868517,  777144,  771997,
    840640,  687715,  670884,  724387,  699534,  811906,  813718,  751746,
    811940,  665031,  977944,  747018,  868814,  761836,  822203,  820568,
    773873,  694939,  1109585, 764019,  837420,  708661,  794921,  815035,
    666580,  794766,  908916,  847270,  821476,  664028,  692455,  797546,
    768376,  1087574, 906441,  867234,  850865,  758540,  691945,  776908,
    633097,  1230024, 1014151, 910644,  1103813, 986635,  1045155, 861992,
    934198,  983519,  811179,  962179,  792938,  933503,  880234,  812130,
    874409,  883276,  795839,  989713,  939256,  937781,  841576,  815385,
    730534,  839408,  755347,  939127,  959799,  794500,  862976,  715332,
    776318,  694732,  728388,  820584,  1103492, 907138,  888491,  869576,
    716593,  839620,  752652,  686934,  791698,  655201,  790225,  717877,
    1094740, 985600,  882236,  881365,  861322,  829889,  744719,  703629,
    751977,  816371,  709909,  789494,  706601,  772415,  751319,  620091,
    1071485, 902540,  810236,  839719,  690109,  810733,  772481,  631228,
    768839,  936618,  879795,  689370,  648709,  708047,  671376,  770407,
    878468,  787245,  649900,  746926,  616131,  633637,  689680,  749796,
    1306271, 1167895, 961945,  938652,  989196,  1044334, 1044736, 857438,
    1047014, 1041409, 1223708, 1095604, 980450,  959719,  766075,  823371,
    876559,  788678,  1171279, 983714,  931687,  836645,  750714,  885783,
    727969,  783972,  688796,  1135949, 955465,  891057,  888173,  818138,
    813717,  726979,  815983,  928238,  727995,  789484,  771771,  688921,
    832505,  828435,  703662,  646581,  922593,  763589,  874793,  855293,
    745832,  806059,  663754,  646314,  1045495, 860713,  785544,  833250,
    687862,  730274,  791344,  745027,  612125,  664809,  748160,  1068761,
    905072,  744400,  835031,  807519,  767652,  762852,  722298,  784809,
    747602,  815011,  671396,  791148,  650881,  784999,  665826,  1046114,
    935024,  814154,  816387,  747539,  668355,  1165731, 956343,  909020,
    992652,  884439,  835671,  990610,  976449,  979100,  801495,  909940,
    748347,  882499,  830128,  853545,  767983,  830741,  684654,  1111436,
    996830,  772324,  840082,  752876,  680602,  794161,  711048,  647810,
    792378,  793638,  650147,  911216,  866197,  820969,  816181,  813948,
    667596,  693931,  795977,  772552,  688817,  693421,  879295,  837042,
    794190,  788716,  748942,  614493,  633485,  753735,  1045745, 937486,
    812256,  816336,  728851,  745050,  767532,  687591,  608984,  672937,
    649571,  711733,  597252,  631149,  707398,  856960,  767920,  729656,
    769700,  763003,  598534,  744645,  725342,  833082,  635166,  752184,
    745660,  609743,  706306,  634615,  793020,  650835,  711505,  690546,
    742240,  665055,  631674,  706891,  705856,  1191048, 1194116, 912563,
    1070804, 964121,  1040284, 1014453, 1191660, 984999,  901232,  956273,
    937041,  813821,  898229,  789937,  850764,  700950,  959135,  911259,
    911946,  854794,  856608,  704946,  690656,  812936,  814469,  732752,
    933887,  771672,  889853,  716286,  750584,  792667,  1067205, 884535,
    858716,  708472,  841971,  814322,  793001,  764312,  770606,  960213,
    898314,  741180,  854996,  747794,  807749,  666100,  805628,  661652,
    722720,  762430,  627700,  683836,  856278,  814727,  730771,  794573,
    767750,  770612,  690465,  746390,  670679,  726550,  728115,  599805,
    1043587, 784160,  835707,  723764,  787877,  784151,  616549,  742665,
    614372,  1014512, 851316,  794646,  764937,  650497,  615290,  723555,
    595089,  851990,  700423,  794678,  772705,  684548,  725966,  751541,
    615551,  725712,  1399182, 1398091, 1145413, 1047191, 890873,  886794,
    912032,  990147,  801078,  837085,  744837,  701655,  933998,  887031,
    707969,  839136,  747850,  792401,  707915,  1092951, 872947,  715762,
    695710,  757492,  713006,  636628,  880918,  835307,  687829,  745372,
    669681,  771383,  748349,  674645,  875113,  832734,  644513,  664377,
    744222,  815584,  892144,  749841,  746464,  610952,  704941,  704613,
    577617,  707376,  817691,  728950,  771815,  632412,  745274,  646474,
    723543,  650243,  996850,  814406,  831150,  830916,  681501,  747918,
    749672,  746787,  706894,  578327,  728525,  706229,  578332,  1000947,
    745433,  634921,  746210,  631798,  707518,  581068,  1390038, 1246094,
    954427,  1107286, 1044971, 1038532, 852144,  886429,  1016886, 987738,
    808904,  1165515, 957428,  979864,  875619,  932569,  748445,  875325,
    741188,  1110548, 996877,  933835,  727635,  861277,  707802,  792607,
    711274,  815517,  793943,  1082526, 748105,  775910,  774363,  797839,
    771836,  633270,  772957,  694361,  881209,  724598,  822963,  794872,
    710949,  705052,  637258,  755089,  1041246, 875054,  785073,  831811,
    684285,  811308,  744230,  745399,  611894,  742257,  610966,  671331,
    991429,  829697,  650376,  774415,  743564,  611105,  666993,  633555,
    725993,  703167,  630392,  761036,  682112,  599377,  668812,  723570,
    599906,  891145,  745239,  790923,  773615,  691324,  670045,  580239,
    705253,  579872,  635214,  891934,  681787,  795081,  689985,  665326,
    709232,  599017,  708157,  632268,  1961753, 1607029, 1642544, 1346537,
    1472637, 1563816, 1524892, 1470744, 1315153, 1141975, 1431231, 1440153,
    1247792, 1339119, 1306580, 1071023, 1108716, 1165811, 1204287, 951680,
    1171022, 960848,  1051687, 1555640, 1074596, 1018538, 1082261, 963917,
    1112092, 1137579, 1108326, 992466,  1275646, 1142701, 1023572, 1118182,
    1118208, 999300,  890919,  1468633, 1459875, 1204532, 943756,  1026017,
    937673,  1081412, 1043655, 946520,  1225925, 1164870, 955272,  1046573,
    1139727, 903793,  1039289, 940897,  957363,  1045675, 1086389, 1050262,
    860517,  934321,  836340,  913405,  817384,  1423938, 1276206, 1111805,
    965434,  834269,  1015259, 1387258, 1107845, 1109593, 1085218, 1047134,
    859037,  988181,  808577,  1393261, 1142536, 1165086, 953901,  1083706,
    858796,  1018331, 836081,  886658,  815044,  1457928, 1226777, 1276394,
    1072125, 1162767, 960791,  1049210, 1094354, 899996,  982801,  958829,
    1034290, 1029423, 1031108, 921885,  978793,  975711,  982409,  885090,
    934919,  831969,  985719,  882763,  978965,  927742,  931074,  765425,
    1266382, 1136277, 995256,  748720,  816311,  935583,  909070,  745834,
    909849,  750018,  1036076, 984570,  965591,  927964,  760520,  830035,
    879694,  883952,  797402,  1028406, 878273,  925093,  896142,  900106,
    735888,  871930,  875841,  929779,  908684,  814059,  858447,  834705,
    1190536, 1009105, 933303,  896883,  739175,  877170,  854338,  1164564,
    956424,  977355,  978821,  933928,  747991,  880809,  682459,  857665,
    1042315, 932089,  811120,  881308,  873934,  716881,  828428,  680017,
    743282,  684812,  1562355, 1398025, 1220272, 1180838, 1172585, 941344,
    1114634, 1072611, 1093945, 979561,  990973,  979934,  963797,  789217,
    860963,  829574,  1245217, 937831,  990847,  814331,  970334,  792551,
    943433,  930584,  794326,  729128,  1019114, 837938,  947217,  756000,
    910484,  749279,  863913,  772777,  733138,  864831,  863631,  710661,
    772620,  1170839, 983948,  882489,  916866,  787601,  836087,  687616,
    775647,  745068,  1166664, 959617,  877186,  718049,  684146,  745250,
    833643,  832978,  887068,  730300,  777984,  838816,  690800,  686278,
    709161,  815443,  791699,  793270,  793204,  712182,  940510,  789821,
    907599,  731659,  853250,  817779,  671769,  747622,  725912,  816999,
    1111250, 998002,  884931,  865593,  753396,  683816,  790763,  790226,
    648888,  790575,  710065,  887048,  729938,  837131,  831007,  683440,
    743287,  649978,  790139,  1510566, 935917,  1143495, 1025026, 907670,
    1083993, 969989,  884280,  1271382, 1070197, 996705,  1000252, 894148,
    956914,  816261,  841038,  741301,  821574,  872739,  846875,  918289,
    911939,  916223,  745471,  868930,  866406,  867364,  707995,  965289,
    894525,  946930,  850913,  753676,  870241,  711866,  844950,  928459,
    861063,  746643,  814816,  754655,  813599,  664149,  818797,  817800,
    670884,  1137518, 909985,  819410,  860255,  699534,  772356,  813718,
    812213,  1084124, 886318,  781453,  694278,  777001,  1109585, 1109634,
    837420,  773684,  794921,  791969,  648276,  973806,  904461,  704175,
    811582,  791873,  630212,  693759,  771262,  1082225, 906441,  908850,
    868641,  691710,  819980,  734981,  630533,  793596,  713544,  776908,
    633527,  1199076, 1306432, 1145810, 993580,  905652,  1046196, 964195,
    942556,  1096984, 1032558, 851187,  983519,  925975,  927741,  789296,
    1169250, 961578,  886913,  841576,  882067,  839730,  860823,  841818,
    939127,  1019517, 916901,  756252,  892595,  867542,  776318,  865346,
    752726,  676573,  734839,  888491,  731480,  868675,  775075,  840511,
    691942,  791698,  674532,  787012,  926396,  791536,  857753,  832592,
    835297,  685760,  744719,  788762,  810821,  783730,  651397,  1040679,
    881086,  837390,  709909,  788065,  613016,  749866,  956694,  860193,
    709972,  671116,  789119,  651297,  769156,  683008,  768839,  879795,
    789885,  838727,  672061,  792655,  652306,  710730,  771708,  667397,
    1046118, 860786,  821758,  709355,  786888,  746926,  750595,  674864,
    1459996, 1306271, 1167895, 961945,  1041029, 1074614, 1043069, 857438,
    930657,  1041409, 1229167, 1012020, 1031147, 960885,  930727,  921943,
    744445,  780541,  881406,  1168539, 983714,  880261,  909498,  911726,
    812165,  722092,  835307,  686988,  858802,  767092,  686640,  960787,
    792108,  754235,  791715,  726979,  811375,  811552,  1104446, 925410,
    829020,  789484,  835578,  835781,  788778,  650605,  814207,  727791,
    784133,  906054,  723685,  855293,  765842,  745832,  786319,  701988,
    784473,  646314,  1043455, 723195,  833250,  748409,  816582,  784702,
    1076436, 886299,  897570,  744400,  851577,  837849,  691466,  669808,
    785869,  761796,  680242,  768970,  1048355, 1043293, 875524,  784809,
    646195,  665883,  769153,  746289,  746701,  875292,  720094,  833738,
    748509,  648263,  644284,  699028,  768058,  612471,  665099,  1390741,
    1164549, 956343,  1049960, 1043416, 931664,  911982,  814518,  748347,
    790345,  715492,  682064,  767983,  827679,  750352,  933668,  886525,
    886795,  866628,  746084,  794161,  711048,  790984,  707634,  793638,
    866197,  776767,  845309,  694141,  813948,  654421,  1050188, 790841,
    822074,  794314,  787690,  644437,  748942,  671594,  693035,  611003,
    750794,  619126,  721603,  683730,  785434,  641569,  744264,  608984,
    666604,  991625,  748335,  705673,  577979,  725723,  582860,  1018826,
    793310,  652082,  708484,  688988,  625310,  727215,  652985,  667745,
    594908,  598286,  652052,  792542,  794980,  649025,  615204,  745660,
    609743,  707587,  814762,  829102,  771101,  744485,  665055,  727960,
    651126,  631548,  580670,  1420658, 1420177, 1169507, 1134490, 993191,
    1046698, 1012208, 1191660, 826395,  789438,  898229,  740403,  805719,
    767222,  878617,  725950,  700950,  959901,  886174,  860349,  768284,
    812809,  1114664, 1109574, 734618,  656873,  713939,  818883,  732096,
    794723,  654076,  655376,  856680,  770444,  813725,  808729,  722823,
    767312,  693856,  1068421, 898314,  854996,  666100,  727521,  805628,
    763300,  782419,  647064,  705727,  762430,  838054,  912674,  856278,
    690465,  764409,  750795,  596168,  878992,  746693,  764502,  630798,
    612316,  662653,  852772,  730053,  768344,  770399,  633066,  688921,
    685640,  725066,  745253,  669063,  723739,  764093,  671892,  794678,
    772705,  725966,  596897,  751541,  596169,  1251925, 1168106, 958285,
    1051930, 862303,  855668,  993689,  1170202, 932553,  837085,  883738,
    766849,  913104,  933222,  889079,  727985,  833691,  682000,  710112,
    649818,  711863,  749615,  872947,  868036,  715762,  674772,  695411,
    655180,  635726,  690572,  860001,  880918,  790289,  752007,  793433,
    789470,  706008,  613333,  772617,  690928,  753236,  856542,  786730,
    812940,  788715,  743363,  742478,  765484,  609888,  794971,  651713,
    694713,  748316,  704613,  631662,  631170,  857048,  851946,  702589,
    728950,  794707,  652755,  745355,  665701,  996850,  814406,  892921,
    633605,  671691,  578327,  633356,  728525,  578598,  704293,  578332,
    633590,  894569,  831719,  653126,  714536,  693505,  613172,  747474,
    705752,  709739,  707518,  635654,  1165963, 954427,  1108326, 1044971,
    1039990, 913688,  987738,  882152,  1163591, 1044784, 875619,  911806,
    913055,  748445,  814932,  790502,  861095,  828913,  836115,  885998,
    864926,  837249,  830347,  682065,  745593,  668521,  706944,  748105,
    674758,  732952,  637314,  797839,  655213,  774444,  636938,  1051543,
    939723,  822963,  733515,  671963,  612177,  622175,  831514,  684285,
    745823,  779996,  699558,  745399,  760929,  627212,  740682,  815197,
    829697,  792463,  749176,  706670,  579491,  653769,  630392,  839396,
    912855,  854577,  764861,  814733,  794103,  731186,  599377,  595360,
    727178,  891145,  681640,  791790,  710043,  773615,  691324,  667528,
    725563,  597823,  704253,  995913,  819845,  795081,  711686,  707517,
    727379,  632268,  708679};
int main() {
  for (int i = 2; i <= MX; i++) {
    if (d[i] == 0) {
      d[i] = i;
      p.push_back(i);
      obr(i);
    }
    for (int j = 0; j < (int)(p).size() && p[j] <= d[i] && p[j] * i <= MX;
         j++) {
      d[p[j] * i] = p[j];
    }
  }
  for (int i = 0; i <= MX; i++) {
    for (int j = 0; j < 5; j++) {
      sort((ls[i][j]).begin(), (ls[i][j]).end());
      ls[i][j].resize(unique((ls[i][j]).begin(), (ls[i][j]).end()) -
                      ls[i][j].begin());
    }
  }
  int T;
  scanf("%d", &T);
  while (T-- > 0) {
    int p0;
    scanf("%d", &p0);
    if (p0 >= 9999) {
      for (int i = 0; i < (int)(p).size(); i++)
        if (p[i] == p0) {
          cout << a[i - 9592 + 8363] << endl;
          break;
        }
      continue;
    }
    vector<int> vv;
    vector<vector<int> > a;
    while (p0 > 0) {
      vv.push_back(p0 % 10);
      p0 /= 10;
    }
    reverse((vv).begin(), (vv).end());
    a.push_back(vv);
    for (int i = 1; i < (int)(vv).size(); i++) {
      vector<int> v0;
      v0.push_back(vv[i]);
      for (int j = 1; j < (int)(vv).size(); j++) {
        v0.push_back(0);
      }
      a.push_back(v0);
    }
    int hh = go(a, 1);
    cout << hh << endl;
  }
  return 0;
}