4.4BSD/usr/src/contrib/calc-1.26.4/lib/lucas_chk.cal

/*
 * Copyright (c) 1993 Landon Curt Noll
 * Permission is granted to use, distribute, or modify this source,
 * provided that this copyright notice remains intact.
 *
 * By: Landon Curt Noll
 *     chongo@toad.com  -or-  ...!{pyramid,sun,uunet}!hoptoad!chongo
 *
 *
 * primes of the form h*2^n-1 for 1<=h<200 and 1<=n<1000
 *
 * For all 0 <= i < prime_cnt, h_p[i]*2^n_p[i]-1 is prime.
 *
 * These values were taken from:
 *
 *	"Prime numbers and Computer Methods for Factorization", by Hans Riesel,
 *	Birkhauser, 1985, pp 384-387.
 *
 * This routine assumes that the file "lucas.cal" has been loaded.
 *
 * NOTE: There are several errors in Riesel's table that have been corrected
 *	 in this file:
 *
 *		193*2^87-1 is prime
 *		193*2^97-1 is NOT prime
 *		199*2^211-1 is prime
 *		199*2^221-1 is NOT prime
 */

global prime_cnt;	/* number of primes in the list */
prime_cnt = 1145;
mat h_p[prime_cnt];	/* h = prime parameters */
mat n_p[prime_cnt];	/* n (exponent) prime parameters */
h_p[0]=1;	n_p[0]=2;
h_p[1]=1;	n_p[1]=3;
h_p[2]=1;	n_p[2]=5;
h_p[3]=1;	n_p[3]=7;
h_p[4]=1;	n_p[4]=13;
h_p[5]=1;	n_p[5]=17;
h_p[6]=1;	n_p[6]=19;
h_p[7]=1;	n_p[7]=31;
h_p[8]=1;	n_p[8]=61;
h_p[9]=1;	n_p[9]=89;
h_p[10]=1;	n_p[10]=107;
h_p[11]=1;	n_p[11]=127;
h_p[12]=1;	n_p[12]=521;
h_p[13]=1;	n_p[13]=607;
h_p[14]=3;	n_p[14]=1;
h_p[15]=3;	n_p[15]=2;
h_p[16]=3;	n_p[16]=3;
h_p[17]=3;	n_p[17]=4;
h_p[18]=3;	n_p[18]=6;
h_p[19]=3;	n_p[19]=7;
h_p[20]=3;	n_p[20]=11;
h_p[21]=3;	n_p[21]=18;
h_p[22]=3;	n_p[22]=34;
h_p[23]=3;	n_p[23]=38;
h_p[24]=3;	n_p[24]=43;
h_p[25]=3;	n_p[25]=55;
h_p[26]=3;	n_p[26]=64;
h_p[27]=3;	n_p[27]=76;
h_p[28]=3;	n_p[28]=94;
h_p[29]=3;	n_p[29]=103;
h_p[30]=3;	n_p[30]=143;
h_p[31]=3;	n_p[31]=206;
h_p[32]=3;	n_p[32]=216;
h_p[33]=3;	n_p[33]=306;
h_p[34]=3;	n_p[34]=324;
h_p[35]=3;	n_p[35]=391;
h_p[36]=3;	n_p[36]=458;
h_p[37]=3;	n_p[37]=470;
h_p[38]=3;	n_p[38]=827;
h_p[39]=5;	n_p[39]=2;
h_p[40]=5;	n_p[40]=4;
h_p[41]=5;	n_p[41]=8;
h_p[42]=5;	n_p[42]=10;
h_p[43]=5;	n_p[43]=12;
h_p[44]=5;	n_p[44]=14;
h_p[45]=5;	n_p[45]=18;
h_p[46]=5;	n_p[46]=32;
h_p[47]=5;	n_p[47]=48;
h_p[48]=5;	n_p[48]=54;
h_p[49]=5;	n_p[49]=72;
h_p[50]=5;	n_p[50]=148;
h_p[51]=5;	n_p[51]=184;
h_p[52]=5;	n_p[52]=248;
h_p[53]=5;	n_p[53]=270;
h_p[54]=5;	n_p[54]=274;
h_p[55]=5;	n_p[55]=420;
h_p[56]=7;	n_p[56]=1;
h_p[57]=7;	n_p[57]=5;
h_p[58]=7;	n_p[58]=9;
h_p[59]=7;	n_p[59]=17;
h_p[60]=7;	n_p[60]=21;
h_p[61]=7;	n_p[61]=29;
h_p[62]=7;	n_p[62]=45;
h_p[63]=7;	n_p[63]=177;
h_p[64]=9;	n_p[64]=1;
h_p[65]=9;	n_p[65]=3;
h_p[66]=9;	n_p[66]=7;
h_p[67]=9;	n_p[67]=13;
h_p[68]=9;	n_p[68]=15;
h_p[69]=9;	n_p[69]=21;
h_p[70]=9;	n_p[70]=43;
h_p[71]=9;	n_p[71]=63;
h_p[72]=9;	n_p[72]=99;
h_p[73]=9;	n_p[73]=109;
h_p[74]=9;	n_p[74]=159;
h_p[75]=9;	n_p[75]=211;
h_p[76]=9;	n_p[76]=309;
h_p[77]=9;	n_p[77]=343;
h_p[78]=9;	n_p[78]=415;
h_p[79]=9;	n_p[79]=469;
h_p[80]=9;	n_p[80]=781;
h_p[81]=9;	n_p[81]=871;
h_p[82]=9;	n_p[82]=939;
h_p[83]=11;	n_p[83]=2;
h_p[84]=11;	n_p[84]=26;
h_p[85]=11;	n_p[85]=50;
h_p[86]=11;	n_p[86]=54;
h_p[87]=11;	n_p[87]=126;
h_p[88]=11;	n_p[88]=134;
h_p[89]=11;	n_p[89]=246;
h_p[90]=11;	n_p[90]=354;
h_p[91]=11;	n_p[91]=362;
h_p[92]=11;	n_p[92]=950;
h_p[93]=13;	n_p[93]=3;
h_p[94]=13;	n_p[94]=7;
h_p[95]=13;	n_p[95]=23;
h_p[96]=13;	n_p[96]=287;
h_p[97]=13;	n_p[97]=291;
h_p[98]=13;	n_p[98]=795;
h_p[99]=15;	n_p[99]=1;
h_p[100]=15;	n_p[100]=2;
h_p[101]=15;	n_p[101]=4;
h_p[102]=15;	n_p[102]=5;
h_p[103]=15;	n_p[103]=10;
h_p[104]=15;	n_p[104]=14;
h_p[105]=15;	n_p[105]=17;
h_p[106]=15;	n_p[106]=31;
h_p[107]=15;	n_p[107]=41;
h_p[108]=15;	n_p[108]=73;
h_p[109]=15;	n_p[109]=80;
h_p[110]=15;	n_p[110]=82;
h_p[111]=15;	n_p[111]=116;
h_p[112]=15;	n_p[112]=125;
h_p[113]=15;	n_p[113]=145;
h_p[114]=15;	n_p[114]=157;
h_p[115]=15;	n_p[115]=172;
h_p[116]=15;	n_p[116]=202;
h_p[117]=15;	n_p[117]=224;
h_p[118]=15;	n_p[118]=266;
h_p[119]=15;	n_p[119]=289;
h_p[120]=15;	n_p[120]=293;
h_p[121]=15;	n_p[121]=463;
h_p[122]=17;	n_p[122]=2;
h_p[123]=17;	n_p[123]=4;
h_p[124]=17;	n_p[124]=6;
h_p[125]=17;	n_p[125]=16;
h_p[126]=17;	n_p[126]=20;
h_p[127]=17;	n_p[127]=36;
h_p[128]=17;	n_p[128]=54;
h_p[129]=17;	n_p[129]=60;
h_p[130]=17;	n_p[130]=96;
h_p[131]=17;	n_p[131]=124;
h_p[132]=17;	n_p[132]=150;
h_p[133]=17;	n_p[133]=252;
h_p[134]=17;	n_p[134]=356;
h_p[135]=17;	n_p[135]=460;
h_p[136]=17;	n_p[136]=612;
h_p[137]=17;	n_p[137]=654;
h_p[138]=17;	n_p[138]=664;
h_p[139]=17;	n_p[139]=698;
h_p[140]=17;	n_p[140]=702;
h_p[141]=17;	n_p[141]=972;
h_p[142]=19;	n_p[142]=1;
h_p[143]=19;	n_p[143]=3;
h_p[144]=19;	n_p[144]=5;
h_p[145]=19;	n_p[145]=21;
h_p[146]=19;	n_p[146]=41;
h_p[147]=19;	n_p[147]=49;
h_p[148]=19;	n_p[148]=89;
h_p[149]=19;	n_p[149]=133;
h_p[150]=19;	n_p[150]=141;
h_p[151]=19;	n_p[151]=165;
h_p[152]=19;	n_p[152]=189;
h_p[153]=19;	n_p[153]=293;
h_p[154]=19;	n_p[154]=305;
h_p[155]=19;	n_p[155]=395;
h_p[156]=19;	n_p[156]=651;
h_p[157]=19;	n_p[157]=665;
h_p[158]=19;	n_p[158]=771;
h_p[159]=19;	n_p[159]=801;
h_p[160]=19;	n_p[160]=923;
h_p[161]=19;	n_p[161]=953;
h_p[162]=21;	n_p[162]=1;
h_p[163]=21;	n_p[163]=2;
h_p[164]=21;	n_p[164]=3;
h_p[165]=21;	n_p[165]=7;
h_p[166]=21;	n_p[166]=10;
h_p[167]=21;	n_p[167]=13;
h_p[168]=21;	n_p[168]=18;
h_p[169]=21;	n_p[169]=27;
h_p[170]=21;	n_p[170]=37;
h_p[171]=21;	n_p[171]=51;
h_p[172]=21;	n_p[172]=74;
h_p[173]=21;	n_p[173]=157;
h_p[174]=21;	n_p[174]=271;
h_p[175]=21;	n_p[175]=458;
h_p[176]=21;	n_p[176]=530;
h_p[177]=21;	n_p[177]=891;
h_p[178]=23;	n_p[178]=4;
h_p[179]=23;	n_p[179]=6;
h_p[180]=23;	n_p[180]=12;
h_p[181]=23;	n_p[181]=46;
h_p[182]=23;	n_p[182]=72;
h_p[183]=23;	n_p[183]=244;
h_p[184]=23;	n_p[184]=264;
h_p[185]=23;	n_p[185]=544;
h_p[186]=23;	n_p[186]=888;
h_p[187]=25;	n_p[187]=3;
h_p[188]=25;	n_p[188]=9;
h_p[189]=25;	n_p[189]=11;
h_p[190]=25;	n_p[190]=17;
h_p[191]=25;	n_p[191]=23;
h_p[192]=25;	n_p[192]=35;
h_p[193]=25;	n_p[193]=39;
h_p[194]=25;	n_p[194]=75;
h_p[195]=25;	n_p[195]=105;
h_p[196]=25;	n_p[196]=107;
h_p[197]=25;	n_p[197]=155;
h_p[198]=25;	n_p[198]=215;
h_p[199]=25;	n_p[199]=335;
h_p[200]=25;	n_p[200]=635;
h_p[201]=25;	n_p[201]=651;
h_p[202]=25;	n_p[202]=687;
h_p[203]=27;	n_p[203]=1;
h_p[204]=27;	n_p[204]=2;
h_p[205]=27;	n_p[205]=4;
h_p[206]=27;	n_p[206]=5;
h_p[207]=27;	n_p[207]=8;
h_p[208]=27;	n_p[208]=10;
h_p[209]=27;	n_p[209]=14;
h_p[210]=27;	n_p[210]=28;
h_p[211]=27;	n_p[211]=37;
h_p[212]=27;	n_p[212]=38;
h_p[213]=27;	n_p[213]=70;
h_p[214]=27;	n_p[214]=121;
h_p[215]=27;	n_p[215]=122;
h_p[216]=27;	n_p[216]=160;
h_p[217]=27;	n_p[217]=170;
h_p[218]=27;	n_p[218]=253;
h_p[219]=27;	n_p[219]=329;
h_p[220]=27;	n_p[220]=362;
h_p[221]=27;	n_p[221]=454;
h_p[222]=27;	n_p[222]=485;
h_p[223]=27;	n_p[223]=500;
h_p[224]=27;	n_p[224]=574;
h_p[225]=27;	n_p[225]=892;
h_p[226]=27;	n_p[226]=962;
h_p[227]=29;	n_p[227]=4;
h_p[228]=29;	n_p[228]=16;
h_p[229]=29;	n_p[229]=76;
h_p[230]=29;	n_p[230]=148;
h_p[231]=29;	n_p[231]=184;
h_p[232]=31;	n_p[232]=1;
h_p[233]=31;	n_p[233]=5;
h_p[234]=31;	n_p[234]=7;
h_p[235]=31;	n_p[235]=11;
h_p[236]=31;	n_p[236]=13;
h_p[237]=31;	n_p[237]=23;
h_p[238]=31;	n_p[238]=33;
h_p[239]=31;	n_p[239]=35;
h_p[240]=31;	n_p[240]=37;
h_p[241]=31;	n_p[241]=47;
h_p[242]=31;	n_p[242]=115;
h_p[243]=31;	n_p[243]=205;
h_p[244]=31;	n_p[244]=235;
h_p[245]=31;	n_p[245]=271;
h_p[246]=31;	n_p[246]=409;
h_p[247]=31;	n_p[247]=739;
h_p[248]=31;	n_p[248]=837;
h_p[249]=31;	n_p[249]=887;
h_p[250]=33;	n_p[250]=2;
h_p[251]=33;	n_p[251]=3;
h_p[252]=33;	n_p[252]=6;
h_p[253]=33;	n_p[253]=8;
h_p[254]=33;	n_p[254]=10;
h_p[255]=33;	n_p[255]=22;
h_p[256]=33;	n_p[256]=35;
h_p[257]=33;	n_p[257]=42;
h_p[258]=33;	n_p[258]=43;
h_p[259]=33;	n_p[259]=46;
h_p[260]=33;	n_p[260]=56;
h_p[261]=33;	n_p[261]=91;
h_p[262]=33;	n_p[262]=102;
h_p[263]=33;	n_p[263]=106;
h_p[264]=33;	n_p[264]=142;
h_p[265]=33;	n_p[265]=190;
h_p[266]=33;	n_p[266]=208;
h_p[267]=33;	n_p[267]=266;
h_p[268]=33;	n_p[268]=330;
h_p[269]=33;	n_p[269]=360;
h_p[270]=33;	n_p[270]=382;
h_p[271]=33;	n_p[271]=462;
h_p[272]=33;	n_p[272]=503;
h_p[273]=33;	n_p[273]=815;
h_p[274]=35;	n_p[274]=2;
h_p[275]=35;	n_p[275]=6;
h_p[276]=35;	n_p[276]=10;
h_p[277]=35;	n_p[277]=20;
h_p[278]=35;	n_p[278]=44;
h_p[279]=35;	n_p[279]=114;
h_p[280]=35;	n_p[280]=146;
h_p[281]=35;	n_p[281]=156;
h_p[282]=35;	n_p[282]=174;
h_p[283]=35;	n_p[283]=260;
h_p[284]=35;	n_p[284]=306;
h_p[285]=35;	n_p[285]=380;
h_p[286]=35;	n_p[286]=654;
h_p[287]=35;	n_p[287]=686;
h_p[288]=35;	n_p[288]=702;
h_p[289]=35;	n_p[289]=814;
h_p[290]=35;	n_p[290]=906;
h_p[291]=37;	n_p[291]=1;
h_p[292]=39;	n_p[292]=3;
h_p[293]=39;	n_p[293]=24;
h_p[294]=39;	n_p[294]=105;
h_p[295]=39;	n_p[295]=153;
h_p[296]=39;	n_p[296]=188;
h_p[297]=39;	n_p[297]=605;
h_p[298]=39;	n_p[298]=795;
h_p[299]=39;	n_p[299]=813;
h_p[300]=39;	n_p[300]=839;
h_p[301]=41;	n_p[301]=2;
h_p[302]=41;	n_p[302]=10;
h_p[303]=41;	n_p[303]=14;
h_p[304]=41;	n_p[304]=18;
h_p[305]=41;	n_p[305]=50;
h_p[306]=41;	n_p[306]=114;
h_p[307]=41;	n_p[307]=122;
h_p[308]=41;	n_p[308]=294;
h_p[309]=41;	n_p[309]=362;
h_p[310]=41;	n_p[310]=554;
h_p[311]=41;	n_p[311]=582;
h_p[312]=41;	n_p[312]=638;
h_p[313]=41;	n_p[313]=758;
h_p[314]=43;	n_p[314]=7;
h_p[315]=43;	n_p[315]=31;
h_p[316]=43;	n_p[316]=67;
h_p[317]=43;	n_p[317]=251;
h_p[318]=43;	n_p[318]=767;
h_p[319]=45;	n_p[319]=1;
h_p[320]=45;	n_p[320]=2;
h_p[321]=45;	n_p[321]=3;
h_p[322]=45;	n_p[322]=4;
h_p[323]=45;	n_p[323]=5;
h_p[324]=45;	n_p[324]=6;
h_p[325]=45;	n_p[325]=8;
h_p[326]=45;	n_p[326]=9;
h_p[327]=45;	n_p[327]=14;
h_p[328]=45;	n_p[328]=15;
h_p[329]=45;	n_p[329]=16;
h_p[330]=45;	n_p[330]=22;
h_p[331]=45;	n_p[331]=28;
h_p[332]=45;	n_p[332]=29;
h_p[333]=45;	n_p[333]=36;
h_p[334]=45;	n_p[334]=37;
h_p[335]=45;	n_p[335]=54;
h_p[336]=45;	n_p[336]=59;
h_p[337]=45;	n_p[337]=85;
h_p[338]=45;	n_p[338]=93;
h_p[339]=45;	n_p[339]=117;
h_p[340]=45;	n_p[340]=119;
h_p[341]=45;	n_p[341]=161;
h_p[342]=45;	n_p[342]=189;
h_p[343]=45;	n_p[343]=193;
h_p[344]=45;	n_p[344]=256;
h_p[345]=45;	n_p[345]=308;
h_p[346]=45;	n_p[346]=322;
h_p[347]=45;	n_p[347]=327;
h_p[348]=45;	n_p[348]=411;
h_p[349]=45;	n_p[349]=466;
h_p[350]=45;	n_p[350]=577;
h_p[351]=45;	n_p[351]=591;
h_p[352]=45;	n_p[352]=902;
h_p[353]=45;	n_p[353]=928;
h_p[354]=45;	n_p[354]=946;
h_p[355]=47;	n_p[355]=4;
h_p[356]=47;	n_p[356]=14;
h_p[357]=47;	n_p[357]=70;
h_p[358]=47;	n_p[358]=78;
h_p[359]=49;	n_p[359]=1;
h_p[360]=49;	n_p[360]=5;
h_p[361]=49;	n_p[361]=7;
h_p[362]=49;	n_p[362]=9;
h_p[363]=49;	n_p[363]=13;
h_p[364]=49;	n_p[364]=15;
h_p[365]=49;	n_p[365]=29;
h_p[366]=49;	n_p[366]=33;
h_p[367]=49;	n_p[367]=39;
h_p[368]=49;	n_p[368]=55;
h_p[369]=49;	n_p[369]=81;
h_p[370]=49;	n_p[370]=95;
h_p[371]=49;	n_p[371]=205;
h_p[372]=49;	n_p[372]=279;
h_p[373]=49;	n_p[373]=581;
h_p[374]=49;	n_p[374]=807;
h_p[375]=49;	n_p[375]=813;
h_p[376]=51;	n_p[376]=1;
h_p[377]=51;	n_p[377]=9;
h_p[378]=51;	n_p[378]=10;
h_p[379]=51;	n_p[379]=19;
h_p[380]=51;	n_p[380]=22;
h_p[381]=51;	n_p[381]=57;
h_p[382]=51;	n_p[382]=69;
h_p[383]=51;	n_p[383]=97;
h_p[384]=51;	n_p[384]=141;
h_p[385]=51;	n_p[385]=169;
h_p[386]=51;	n_p[386]=171;
h_p[387]=51;	n_p[387]=195;
h_p[388]=51;	n_p[388]=238;
h_p[389]=51;	n_p[389]=735;
h_p[390]=51;	n_p[390]=885;
h_p[391]=53;	n_p[391]=2;
h_p[392]=53;	n_p[392]=6;
h_p[393]=53;	n_p[393]=8;
h_p[394]=53;	n_p[394]=42;
h_p[395]=53;	n_p[395]=50;
h_p[396]=53;	n_p[396]=62;
h_p[397]=53;	n_p[397]=362;
h_p[398]=53;	n_p[398]=488;
h_p[399]=53;	n_p[399]=642;
h_p[400]=53;	n_p[400]=846;
h_p[401]=55;	n_p[401]=1;
h_p[402]=55;	n_p[402]=3;
h_p[403]=55;	n_p[403]=5;
h_p[404]=55;	n_p[404]=7;
h_p[405]=55;	n_p[405]=15;
h_p[406]=55;	n_p[406]=33;
h_p[407]=55;	n_p[407]=41;
h_p[408]=55;	n_p[408]=57;
h_p[409]=55;	n_p[409]=69;
h_p[410]=55;	n_p[410]=75;
h_p[411]=55;	n_p[411]=77;
h_p[412]=55;	n_p[412]=131;
h_p[413]=55;	n_p[413]=133;
h_p[414]=55;	n_p[414]=153;
h_p[415]=55;	n_p[415]=247;
h_p[416]=55;	n_p[416]=305;
h_p[417]=55;	n_p[417]=351;
h_p[418]=55;	n_p[418]=409;
h_p[419]=55;	n_p[419]=471;
h_p[420]=57;	n_p[420]=1;
h_p[421]=57;	n_p[421]=2;
h_p[422]=57;	n_p[422]=4;
h_p[423]=57;	n_p[423]=5;
h_p[424]=57;	n_p[424]=8;
h_p[425]=57;	n_p[425]=10;
h_p[426]=57;	n_p[426]=20;
h_p[427]=57;	n_p[427]=22;
h_p[428]=57;	n_p[428]=25;
h_p[429]=57;	n_p[429]=26;
h_p[430]=57;	n_p[430]=32;
h_p[431]=57;	n_p[431]=44;
h_p[432]=57;	n_p[432]=62;
h_p[433]=57;	n_p[433]=77;
h_p[434]=57;	n_p[434]=158;
h_p[435]=57;	n_p[435]=317;
h_p[436]=57;	n_p[436]=500;
h_p[437]=57;	n_p[437]=713;
h_p[438]=59;	n_p[438]=12;
h_p[439]=59;	n_p[439]=16;
h_p[440]=59;	n_p[440]=72;
h_p[441]=59;	n_p[441]=160;
h_p[442]=59;	n_p[442]=256;
h_p[443]=59;	n_p[443]=916;
h_p[444]=61;	n_p[444]=3;
h_p[445]=61;	n_p[445]=5;
h_p[446]=61;	n_p[446]=9;
h_p[447]=61;	n_p[447]=13;
h_p[448]=61;	n_p[448]=17;
h_p[449]=61;	n_p[449]=19;
h_p[450]=61;	n_p[450]=25;
h_p[451]=61;	n_p[451]=39;
h_p[452]=61;	n_p[452]=63;
h_p[453]=61;	n_p[453]=67;
h_p[454]=61;	n_p[454]=75;
h_p[455]=61;	n_p[455]=119;
h_p[456]=61;	n_p[456]=147;
h_p[457]=61;	n_p[457]=225;
h_p[458]=61;	n_p[458]=419;
h_p[459]=61;	n_p[459]=715;
h_p[460]=61;	n_p[460]=895;
h_p[461]=63;	n_p[461]=2;
h_p[462]=63;	n_p[462]=3;
h_p[463]=63;	n_p[463]=8;
h_p[464]=63;	n_p[464]=11;
h_p[465]=63;	n_p[465]=14;
h_p[466]=63;	n_p[466]=16;
h_p[467]=63;	n_p[467]=28;
h_p[468]=63;	n_p[468]=32;
h_p[469]=63;	n_p[469]=39;
h_p[470]=63;	n_p[470]=66;
h_p[471]=63;	n_p[471]=68;
h_p[472]=63;	n_p[472]=91;
h_p[473]=63;	n_p[473]=98;
h_p[474]=63;	n_p[474]=116;
h_p[475]=63;	n_p[475]=126;
h_p[476]=63;	n_p[476]=164;
h_p[477]=63;	n_p[477]=191;
h_p[478]=63;	n_p[478]=298;
h_p[479]=63;	n_p[479]=323;
h_p[480]=63;	n_p[480]=443;
h_p[481]=63;	n_p[481]=714;
h_p[482]=63;	n_p[482]=758;
h_p[483]=63;	n_p[483]=759;
h_p[484]=65;	n_p[484]=4;
h_p[485]=65;	n_p[485]=6;
h_p[486]=65;	n_p[486]=12;
h_p[487]=65;	n_p[487]=22;
h_p[488]=65;	n_p[488]=28;
h_p[489]=65;	n_p[489]=52;
h_p[490]=65;	n_p[490]=78;
h_p[491]=65;	n_p[491]=94;
h_p[492]=65;	n_p[492]=124;
h_p[493]=65;	n_p[493]=162;
h_p[494]=65;	n_p[494]=174;
h_p[495]=65;	n_p[495]=192;
h_p[496]=65;	n_p[496]=204;
h_p[497]=65;	n_p[497]=304;
h_p[498]=65;	n_p[498]=376;
h_p[499]=65;	n_p[499]=808;
h_p[500]=65;	n_p[500]=930;
h_p[501]=65;	n_p[501]=972;
h_p[502]=67;	n_p[502]=5;
h_p[503]=67;	n_p[503]=9;
h_p[504]=67;	n_p[504]=21;
h_p[505]=67;	n_p[505]=45;
h_p[506]=67;	n_p[506]=65;
h_p[507]=67;	n_p[507]=77;
h_p[508]=67;	n_p[508]=273;
h_p[509]=67;	n_p[509]=677;
h_p[510]=69;	n_p[510]=1;
h_p[511]=69;	n_p[511]=4;
h_p[512]=69;	n_p[512]=5;
h_p[513]=69;	n_p[513]=7;
h_p[514]=69;	n_p[514]=9;
h_p[515]=69;	n_p[515]=11;
h_p[516]=69;	n_p[516]=13;
h_p[517]=69;	n_p[517]=17;
h_p[518]=69;	n_p[518]=19;
h_p[519]=69;	n_p[519]=23;
h_p[520]=69;	n_p[520]=29;
h_p[521]=69;	n_p[521]=37;
h_p[522]=69;	n_p[522]=49;
h_p[523]=69;	n_p[523]=61;
h_p[524]=69;	n_p[524]=79;
h_p[525]=69;	n_p[525]=99;
h_p[526]=69;	n_p[526]=121;
h_p[527]=69;	n_p[527]=133;
h_p[528]=69;	n_p[528]=141;
h_p[529]=69;	n_p[529]=164;
h_p[530]=69;	n_p[530]=173;
h_p[531]=69;	n_p[531]=181;
h_p[532]=69;	n_p[532]=185;
h_p[533]=69;	n_p[533]=193;
h_p[534]=69;	n_p[534]=233;
h_p[535]=69;	n_p[535]=299;
h_p[536]=69;	n_p[536]=313;
h_p[537]=69;	n_p[537]=351;
h_p[538]=69;	n_p[538]=377;
h_p[539]=69;	n_p[539]=540;
h_p[540]=69;	n_p[540]=569;
h_p[541]=69;	n_p[541]=909;
h_p[542]=71;	n_p[542]=2;
h_p[543]=71;	n_p[543]=14;
h_p[544]=71;	n_p[544]=410;
h_p[545]=73;	n_p[545]=7;
h_p[546]=73;	n_p[546]=11;
h_p[547]=73;	n_p[547]=19;
h_p[548]=73;	n_p[548]=71;
h_p[549]=73;	n_p[549]=79;
h_p[550]=73;	n_p[550]=131;
h_p[551]=75;	n_p[551]=1;
h_p[552]=75;	n_p[552]=3;
h_p[553]=75;	n_p[553]=5;
h_p[554]=75;	n_p[554]=6;
h_p[555]=75;	n_p[555]=18;
h_p[556]=75;	n_p[556]=19;
h_p[557]=75;	n_p[557]=20;
h_p[558]=75;	n_p[558]=22;
h_p[559]=75;	n_p[559]=28;
h_p[560]=75;	n_p[560]=29;
h_p[561]=75;	n_p[561]=39;
h_p[562]=75;	n_p[562]=43;
h_p[563]=75;	n_p[563]=49;
h_p[564]=75;	n_p[564]=75;
h_p[565]=75;	n_p[565]=85;
h_p[566]=75;	n_p[566]=92;
h_p[567]=75;	n_p[567]=111;
h_p[568]=75;	n_p[568]=126;
h_p[569]=75;	n_p[569]=136;
h_p[570]=75;	n_p[570]=159;
h_p[571]=75;	n_p[571]=162;
h_p[572]=75;	n_p[572]=237;
h_p[573]=75;	n_p[573]=349;
h_p[574]=75;	n_p[574]=381;
h_p[575]=75;	n_p[575]=767;
h_p[576]=75;	n_p[576]=969;
h_p[577]=77;	n_p[577]=2;
h_p[578]=77;	n_p[578]=4;
h_p[579]=77;	n_p[579]=14;
h_p[580]=77;	n_p[580]=26;
h_p[581]=77;	n_p[581]=58;
h_p[582]=77;	n_p[582]=60;
h_p[583]=77;	n_p[583]=64;
h_p[584]=77;	n_p[584]=100;
h_p[585]=77;	n_p[585]=122;
h_p[586]=77;	n_p[586]=212;
h_p[587]=77;	n_p[587]=566;
h_p[588]=77;	n_p[588]=638;
h_p[589]=79;	n_p[589]=1;
h_p[590]=79;	n_p[590]=3;
h_p[591]=79;	n_p[591]=7;
h_p[592]=79;	n_p[592]=15;
h_p[593]=79;	n_p[593]=43;
h_p[594]=79;	n_p[594]=57;
h_p[595]=79;	n_p[595]=61;
h_p[596]=79;	n_p[596]=75;
h_p[597]=79;	n_p[597]=145;
h_p[598]=79;	n_p[598]=217;
h_p[599]=79;	n_p[599]=247;
h_p[600]=81;	n_p[600]=3;
h_p[601]=81;	n_p[601]=5;
h_p[602]=81;	n_p[602]=11;
h_p[603]=81;	n_p[603]=17;
h_p[604]=81;	n_p[604]=21;
h_p[605]=81;	n_p[605]=27;
h_p[606]=81;	n_p[606]=81;
h_p[607]=81;	n_p[607]=101;
h_p[608]=81;	n_p[608]=107;
h_p[609]=81;	n_p[609]=327;
h_p[610]=81;	n_p[610]=383;
h_p[611]=81;	n_p[611]=387;
h_p[612]=81;	n_p[612]=941;
h_p[613]=83;	n_p[613]=2;
h_p[614]=83;	n_p[614]=4;
h_p[615]=83;	n_p[615]=8;
h_p[616]=83;	n_p[616]=10;
h_p[617]=83;	n_p[617]=14;
h_p[618]=83;	n_p[618]=18;
h_p[619]=83;	n_p[619]=22;
h_p[620]=83;	n_p[620]=24;
h_p[621]=83;	n_p[621]=26;
h_p[622]=83;	n_p[622]=28;
h_p[623]=83;	n_p[623]=36;
h_p[624]=83;	n_p[624]=42;
h_p[625]=83;	n_p[625]=58;
h_p[626]=83;	n_p[626]=64;
h_p[627]=83;	n_p[627]=78;
h_p[628]=83;	n_p[628]=158;
h_p[629]=83;	n_p[629]=198;
h_p[630]=83;	n_p[630]=206;
h_p[631]=83;	n_p[631]=424;
h_p[632]=83;	n_p[632]=550;
h_p[633]=83;	n_p[633]=676;
h_p[634]=83;	n_p[634]=904;
h_p[635]=85;	n_p[635]=5;
h_p[636]=85;	n_p[636]=11;
h_p[637]=85;	n_p[637]=71;
h_p[638]=85;	n_p[638]=113;
h_p[639]=85;	n_p[639]=115;
h_p[640]=85;	n_p[640]=355;
h_p[641]=85;	n_p[641]=473;
h_p[642]=85;	n_p[642]=563;
h_p[643]=85;	n_p[643]=883;
h_p[644]=87;	n_p[644]=1;
h_p[645]=87;	n_p[645]=2;
h_p[646]=87;	n_p[646]=8;
h_p[647]=87;	n_p[647]=9;
h_p[648]=87;	n_p[648]=10;
h_p[649]=87;	n_p[649]=12;
h_p[650]=87;	n_p[650]=22;
h_p[651]=87;	n_p[651]=29;
h_p[652]=87;	n_p[652]=32;
h_p[653]=87;	n_p[653]=50;
h_p[654]=87;	n_p[654]=57;
h_p[655]=87;	n_p[655]=69;
h_p[656]=87;	n_p[656]=81;
h_p[657]=87;	n_p[657]=122;
h_p[658]=87;	n_p[658]=138;
h_p[659]=87;	n_p[659]=200;
h_p[660]=87;	n_p[660]=296;
h_p[661]=87;	n_p[661]=514;
h_p[662]=87;	n_p[662]=656;
h_p[663]=87;	n_p[663]=682;
h_p[664]=87;	n_p[664]=778;
h_p[665]=87;	n_p[665]=881;
h_p[666]=89;	n_p[666]=4;
h_p[667]=89;	n_p[667]=8;
h_p[668]=89;	n_p[668]=12;
h_p[669]=89;	n_p[669]=24;
h_p[670]=89;	n_p[670]=48;
h_p[671]=89;	n_p[671]=52;
h_p[672]=89;	n_p[672]=64;
h_p[673]=89;	n_p[673]=84;
h_p[674]=89;	n_p[674]=96;
h_p[675]=91;	n_p[675]=1;
h_p[676]=91;	n_p[676]=3;
h_p[677]=91;	n_p[677]=9;
h_p[678]=91;	n_p[678]=13;
h_p[679]=91;	n_p[679]=15;
h_p[680]=91;	n_p[680]=17;
h_p[681]=91;	n_p[681]=19;
h_p[682]=91;	n_p[682]=23;
h_p[683]=91;	n_p[683]=47;
h_p[684]=91;	n_p[684]=57;
h_p[685]=91;	n_p[685]=67;
h_p[686]=91;	n_p[686]=73;
h_p[687]=91;	n_p[687]=77;
h_p[688]=91;	n_p[688]=81;
h_p[689]=91;	n_p[689]=83;
h_p[690]=91;	n_p[690]=191;
h_p[691]=91;	n_p[691]=301;
h_p[692]=91;	n_p[692]=321;
h_p[693]=91;	n_p[693]=435;
h_p[694]=91;	n_p[694]=867;
h_p[695]=91;	n_p[695]=869;
h_p[696]=91;	n_p[696]=917;
h_p[697]=93;	n_p[697]=3;
h_p[698]=93;	n_p[698]=4;
h_p[699]=93;	n_p[699]=7;
h_p[700]=93;	n_p[700]=10;
h_p[701]=93;	n_p[701]=15;
h_p[702]=93;	n_p[702]=18;
h_p[703]=93;	n_p[703]=19;
h_p[704]=93;	n_p[704]=24;
h_p[705]=93;	n_p[705]=27;
h_p[706]=93;	n_p[706]=39;
h_p[707]=93;	n_p[707]=60;
h_p[708]=93;	n_p[708]=84;
h_p[709]=93;	n_p[709]=111;
h_p[710]=93;	n_p[710]=171;
h_p[711]=93;	n_p[711]=192;
h_p[712]=93;	n_p[712]=222;
h_p[713]=93;	n_p[713]=639;
h_p[714]=93;	n_p[714]=954;
h_p[715]=95;	n_p[715]=2;
h_p[716]=95;	n_p[716]=6;
h_p[717]=95;	n_p[717]=26;
h_p[718]=95;	n_p[718]=32;
h_p[719]=95;	n_p[719]=66;
h_p[720]=95;	n_p[720]=128;
h_p[721]=95;	n_p[721]=170;
h_p[722]=95;	n_p[722]=288;
h_p[723]=95;	n_p[723]=320;
h_p[724]=95;	n_p[724]=470;
h_p[725]=97;	n_p[725]=1;
h_p[726]=97;	n_p[726]=9;
h_p[727]=97;	n_p[727]=45;
h_p[728]=97;	n_p[728]=177;
h_p[729]=97;	n_p[729]=585;
h_p[730]=99;	n_p[730]=1;
h_p[731]=99;	n_p[731]=4;
h_p[732]=99;	n_p[732]=5;
h_p[733]=99;	n_p[733]=7;
h_p[734]=99;	n_p[734]=8;
h_p[735]=99;	n_p[735]=11;
h_p[736]=99;	n_p[736]=19;
h_p[737]=99;	n_p[737]=25;
h_p[738]=99;	n_p[738]=28;
h_p[739]=99;	n_p[739]=35;
h_p[740]=99;	n_p[740]=65;
h_p[741]=99;	n_p[741]=79;
h_p[742]=99;	n_p[742]=212;
h_p[743]=99;	n_p[743]=271;
h_p[744]=99;	n_p[744]=361;
h_p[745]=99;	n_p[745]=461;
h_p[746]=101;	n_p[746]=10;
h_p[747]=101;	n_p[747]=18;
h_p[748]=101;	n_p[748]=54;
h_p[749]=101;	n_p[749]=70;
h_p[750]=103;	n_p[750]=3;
h_p[751]=103;	n_p[751]=7;
h_p[752]=103;	n_p[752]=11;
h_p[753]=103;	n_p[753]=19;
h_p[754]=103;	n_p[754]=63;
h_p[755]=103;	n_p[755]=75;
h_p[756]=103;	n_p[756]=95;
h_p[757]=103;	n_p[757]=127;
h_p[758]=103;	n_p[758]=155;
h_p[759]=103;	n_p[759]=163;
h_p[760]=103;	n_p[760]=171;
h_p[761]=103;	n_p[761]=283;
h_p[762]=103;	n_p[762]=563;
h_p[763]=105;	n_p[763]=2;
h_p[764]=105;	n_p[764]=3;
h_p[765]=105;	n_p[765]=5;
h_p[766]=105;	n_p[766]=6;
h_p[767]=105;	n_p[767]=8;
h_p[768]=105;	n_p[768]=9;
h_p[769]=105;	n_p[769]=25;
h_p[770]=105;	n_p[770]=32;
h_p[771]=105;	n_p[771]=65;
h_p[772]=105;	n_p[772]=113;
h_p[773]=105;	n_p[773]=119;
h_p[774]=105;	n_p[774]=155;
h_p[775]=105;	n_p[775]=177;
h_p[776]=105;	n_p[776]=299;
h_p[777]=105;	n_p[777]=335;
h_p[778]=105;	n_p[778]=426;
h_p[779]=105;	n_p[779]=462;
h_p[780]=105;	n_p[780]=617;
h_p[781]=105;	n_p[781]=896;
h_p[782]=107;	n_p[782]=10;
h_p[783]=107;	n_p[783]=12;
h_p[784]=107;	n_p[784]=18;
h_p[785]=107;	n_p[785]=24;
h_p[786]=107;	n_p[786]=28;
h_p[787]=107;	n_p[787]=40;
h_p[788]=107;	n_p[788]=90;
h_p[789]=107;	n_p[789]=132;
h_p[790]=107;	n_p[790]=214;
h_p[791]=107;	n_p[791]=238;
h_p[792]=107;	n_p[792]=322;
h_p[793]=107;	n_p[793]=532;
h_p[794]=107;	n_p[794]=858;
h_p[795]=107;	n_p[795]=940;
h_p[796]=109;	n_p[796]=9;
h_p[797]=109;	n_p[797]=149;
h_p[798]=109;	n_p[798]=177;
h_p[799]=109;	n_p[799]=419;
h_p[800]=109;	n_p[800]=617;
h_p[801]=113;	n_p[801]=8;
h_p[802]=113;	n_p[802]=14;
h_p[803]=113;	n_p[803]=74;
h_p[804]=113;	n_p[804]=80;
h_p[805]=113;	n_p[805]=274;
h_p[806]=113;	n_p[806]=334;
h_p[807]=113;	n_p[807]=590;
h_p[808]=113;	n_p[808]=608;
h_p[809]=113;	n_p[809]=614;
h_p[810]=113;	n_p[810]=650;
h_p[811]=115;	n_p[811]=1;
h_p[812]=115;	n_p[812]=3;
h_p[813]=115;	n_p[813]=11;
h_p[814]=115;	n_p[814]=13;
h_p[815]=115;	n_p[815]=19;
h_p[816]=115;	n_p[816]=21;
h_p[817]=115;	n_p[817]=31;
h_p[818]=115;	n_p[818]=49;
h_p[819]=115;	n_p[819]=59;
h_p[820]=115;	n_p[820]=69;
h_p[821]=115;	n_p[821]=73;
h_p[822]=115;	n_p[822]=115;
h_p[823]=115;	n_p[823]=129;
h_p[824]=115;	n_p[824]=397;
h_p[825]=115;	n_p[825]=623;
h_p[826]=115;	n_p[826]=769;
h_p[827]=119;	n_p[827]=12;
h_p[828]=119;	n_p[828]=16;
h_p[829]=119;	n_p[829]=52;
h_p[830]=119;	n_p[830]=160;
h_p[831]=119;	n_p[831]=192;
h_p[832]=119;	n_p[832]=216;
h_p[833]=119;	n_p[833]=376;
h_p[834]=119;	n_p[834]=436;
h_p[835]=121;	n_p[835]=1;
h_p[836]=121;	n_p[836]=3;
h_p[837]=121;	n_p[837]=21;
h_p[838]=121;	n_p[838]=27;
h_p[839]=121;	n_p[839]=37;
h_p[840]=121;	n_p[840]=43;
h_p[841]=121;	n_p[841]=91;
h_p[842]=121;	n_p[842]=117;
h_p[843]=121;	n_p[843]=141;
h_p[844]=121;	n_p[844]=163;
h_p[845]=121;	n_p[845]=373;
h_p[846]=121;	n_p[846]=421;
h_p[847]=125;	n_p[847]=2;
h_p[848]=125;	n_p[848]=4;
h_p[849]=125;	n_p[849]=44;
h_p[850]=125;	n_p[850]=182;
h_p[851]=125;	n_p[851]=496;
h_p[852]=125;	n_p[852]=904;
h_p[853]=127;	n_p[853]=25;
h_p[854]=127;	n_p[854]=113;
h_p[855]=131;	n_p[855]=2;
h_p[856]=131;	n_p[856]=14;
h_p[857]=131;	n_p[857]=34;
h_p[858]=131;	n_p[858]=38;
h_p[859]=131;	n_p[859]=42;
h_p[860]=131;	n_p[860]=78;
h_p[861]=131;	n_p[861]=90;
h_p[862]=131;	n_p[862]=178;
h_p[863]=131;	n_p[863]=778;
h_p[864]=131;	n_p[864]=974;
h_p[865]=133;	n_p[865]=3;
h_p[866]=133;	n_p[866]=11;
h_p[867]=133;	n_p[867]=15;
h_p[868]=133;	n_p[868]=19;
h_p[869]=133;	n_p[869]=31;
h_p[870]=133;	n_p[870]=59;
h_p[871]=133;	n_p[871]=75;
h_p[872]=133;	n_p[872]=103;
h_p[873]=133;	n_p[873]=163;
h_p[874]=133;	n_p[874]=235;
h_p[875]=133;	n_p[875]=375;
h_p[876]=133;	n_p[876]=615;
h_p[877]=133;	n_p[877]=767;
h_p[878]=137;	n_p[878]=2;
h_p[879]=137;	n_p[879]=18;
h_p[880]=137;	n_p[880]=38;
h_p[881]=137;	n_p[881]=62;
h_p[882]=139;	n_p[882]=1;
h_p[883]=139;	n_p[883]=5;
h_p[884]=139;	n_p[884]=7;
h_p[885]=139;	n_p[885]=9;
h_p[886]=139;	n_p[886]=15;
h_p[887]=139;	n_p[887]=19;
h_p[888]=139;	n_p[888]=21;
h_p[889]=139;	n_p[889]=35;
h_p[890]=139;	n_p[890]=37;
h_p[891]=139;	n_p[891]=39;
h_p[892]=139;	n_p[892]=41;
h_p[893]=139;	n_p[893]=49;
h_p[894]=139;	n_p[894]=69;
h_p[895]=139;	n_p[895]=111;
h_p[896]=139;	n_p[896]=115;
h_p[897]=139;	n_p[897]=141;
h_p[898]=139;	n_p[898]=159;
h_p[899]=139;	n_p[899]=181;
h_p[900]=139;	n_p[900]=201;
h_p[901]=139;	n_p[901]=217;
h_p[902]=139;	n_p[902]=487;
h_p[903]=139;	n_p[903]=567;
h_p[904]=139;	n_p[904]=677;
h_p[905]=139;	n_p[905]=765;
h_p[906]=139;	n_p[906]=811;
h_p[907]=139;	n_p[907]=841;
h_p[908]=139;	n_p[908]=917;
h_p[909]=143;	n_p[909]=2;
h_p[910]=143;	n_p[910]=4;
h_p[911]=143;	n_p[911]=6;
h_p[912]=143;	n_p[912]=8;
h_p[913]=143;	n_p[913]=12;
h_p[914]=143;	n_p[914]=18;
h_p[915]=143;	n_p[915]=26;
h_p[916]=143;	n_p[916]=32;
h_p[917]=143;	n_p[917]=34;
h_p[918]=143;	n_p[918]=36;
h_p[919]=143;	n_p[919]=42;
h_p[920]=143;	n_p[920]=60;
h_p[921]=143;	n_p[921]=78;
h_p[922]=143;	n_p[922]=82;
h_p[923]=143;	n_p[923]=84;
h_p[924]=143;	n_p[924]=88;
h_p[925]=143;	n_p[925]=154;
h_p[926]=143;	n_p[926]=174;
h_p[927]=143;	n_p[927]=208;
h_p[928]=143;	n_p[928]=256;
h_p[929]=143;	n_p[929]=366;
h_p[930]=143;	n_p[930]=448;
h_p[931]=143;	n_p[931]=478;
h_p[932]=143;	n_p[932]=746;
h_p[933]=145;	n_p[933]=5;
h_p[934]=145;	n_p[934]=13;
h_p[935]=145;	n_p[935]=15;
h_p[936]=145;	n_p[936]=31;
h_p[937]=145;	n_p[937]=77;
h_p[938]=145;	n_p[938]=151;
h_p[939]=145;	n_p[939]=181;
h_p[940]=145;	n_p[940]=245;
h_p[941]=145;	n_p[941]=445;
h_p[942]=145;	n_p[942]=447;
h_p[943]=145;	n_p[943]=883;
h_p[944]=149;	n_p[944]=4;
h_p[945]=149;	n_p[945]=16;
h_p[946]=149;	n_p[946]=48;
h_p[947]=149;	n_p[947]=60;
h_p[948]=149;	n_p[948]=240;
h_p[949]=149;	n_p[949]=256;
h_p[950]=149;	n_p[950]=304;
h_p[951]=151;	n_p[951]=5;
h_p[952]=151;	n_p[952]=221;
h_p[953]=151;	n_p[953]=641;
h_p[954]=155;	n_p[954]=2;
h_p[955]=155;	n_p[955]=8;
h_p[956]=155;	n_p[956]=14;
h_p[957]=155;	n_p[957]=16;
h_p[958]=155;	n_p[958]=44;
h_p[959]=155;	n_p[959]=46;
h_p[960]=155;	n_p[960]=82;
h_p[961]=155;	n_p[961]=172;
h_p[962]=155;	n_p[962]=196;
h_p[963]=155;	n_p[963]=254;
h_p[964]=155;	n_p[964]=556;
h_p[965]=155;	n_p[965]=806;
h_p[966]=157;	n_p[966]=1;
h_p[967]=157;	n_p[967]=5;
h_p[968]=157;	n_p[968]=33;
h_p[969]=157;	n_p[969]=121;
h_p[970]=157;	n_p[970]=125;
h_p[971]=157;	n_p[971]=305;
h_p[972]=157;	n_p[972]=445;
h_p[973]=157;	n_p[973]=473;
h_p[974]=157;	n_p[974]=513;
h_p[975]=161;	n_p[975]=2;
h_p[976]=161;	n_p[976]=6;
h_p[977]=161;	n_p[977]=18;
h_p[978]=161;	n_p[978]=22;
h_p[979]=161;	n_p[979]=34;
h_p[980]=161;	n_p[980]=54;
h_p[981]=161;	n_p[981]=98;
h_p[982]=161;	n_p[982]=122;
h_p[983]=161;	n_p[983]=146;
h_p[984]=161;	n_p[984]=222;
h_p[985]=161;	n_p[985]=306;
h_p[986]=161;	n_p[986]=422;
h_p[987]=161;	n_p[987]=654;
h_p[988]=161;	n_p[988]=682;
h_p[989]=161;	n_p[989]=862;
h_p[990]=163;	n_p[990]=3;
h_p[991]=163;	n_p[991]=31;
h_p[992]=163;	n_p[992]=63;
h_p[993]=163;	n_p[993]=303;
h_p[994]=167;	n_p[994]=4;
h_p[995]=167;	n_p[995]=6;
h_p[996]=167;	n_p[996]=8;
h_p[997]=167;	n_p[997]=10;
h_p[998]=167;	n_p[998]=16;
h_p[999]=167;	n_p[999]=32;
h_p[1000]=167;	n_p[1000]=38;
h_p[1001]=167;	n_p[1001]=42;
h_p[1002]=167;	n_p[1002]=52;
h_p[1003]=167;	n_p[1003]=456;
h_p[1004]=167;	n_p[1004]=576;
h_p[1005]=167;	n_p[1005]=668;
h_p[1006]=169;	n_p[1006]=1;
h_p[1007]=169;	n_p[1007]=5;
h_p[1008]=169;	n_p[1008]=11;
h_p[1009]=169;	n_p[1009]=17;
h_p[1010]=169;	n_p[1010]=67;
h_p[1011]=169;	n_p[1011]=137;
h_p[1012]=169;	n_p[1012]=157;
h_p[1013]=169;	n_p[1013]=203;
h_p[1014]=169;	n_p[1014]=209;
h_p[1015]=169;	n_p[1015]=227;
h_p[1016]=169;	n_p[1016]=263;
h_p[1017]=169;	n_p[1017]=917;
h_p[1018]=173;	n_p[1018]=2;
h_p[1019]=173;	n_p[1019]=4;
h_p[1020]=173;	n_p[1020]=6;
h_p[1021]=173;	n_p[1021]=16;
h_p[1022]=173;	n_p[1022]=32;
h_p[1023]=173;	n_p[1023]=50;
h_p[1024]=173;	n_p[1024]=76;
h_p[1025]=173;	n_p[1025]=80;
h_p[1026]=173;	n_p[1026]=96;
h_p[1027]=173;	n_p[1027]=104;
h_p[1028]=173;	n_p[1028]=162;
h_p[1029]=173;	n_p[1029]=212;
h_p[1030]=173;	n_p[1030]=230;
h_p[1031]=173;	n_p[1031]=260;
h_p[1032]=173;	n_p[1032]=480;
h_p[1033]=173;	n_p[1033]=612;
h_p[1034]=175;	n_p[1034]=1;
h_p[1035]=175;	n_p[1035]=3;
h_p[1036]=175;	n_p[1036]=9;
h_p[1037]=175;	n_p[1037]=21;
h_p[1038]=175;	n_p[1038]=23;
h_p[1039]=175;	n_p[1039]=41;
h_p[1040]=175;	n_p[1040]=47;
h_p[1041]=175;	n_p[1041]=57;
h_p[1042]=175;	n_p[1042]=69;
h_p[1043]=175;	n_p[1043]=83;
h_p[1044]=175;	n_p[1044]=193;
h_p[1045]=175;	n_p[1045]=249;
h_p[1046]=175;	n_p[1046]=291;
h_p[1047]=175;	n_p[1047]=421;
h_p[1048]=175;	n_p[1048]=433;
h_p[1049]=175;	n_p[1049]=997;
h_p[1050]=179;	n_p[1050]=8;
h_p[1051]=179;	n_p[1051]=68;
h_p[1052]=179;	n_p[1052]=108;
h_p[1053]=181;	n_p[1053]=3;
h_p[1054]=181;	n_p[1054]=5;
h_p[1055]=181;	n_p[1055]=7;
h_p[1056]=181;	n_p[1056]=9;
h_p[1057]=181;	n_p[1057]=11;
h_p[1058]=181;	n_p[1058]=17;
h_p[1059]=181;	n_p[1059]=23;
h_p[1060]=181;	n_p[1060]=31;
h_p[1061]=181;	n_p[1061]=35;
h_p[1062]=181;	n_p[1062]=43;
h_p[1063]=181;	n_p[1063]=47;
h_p[1064]=181;	n_p[1064]=83;
h_p[1065]=181;	n_p[1065]=85;
h_p[1066]=181;	n_p[1066]=99;
h_p[1067]=181;	n_p[1067]=101;
h_p[1068]=181;	n_p[1068]=195;
h_p[1069]=181;	n_p[1069]=267;
h_p[1070]=181;	n_p[1070]=281;
h_p[1071]=181;	n_p[1071]=363;
h_p[1072]=181;	n_p[1072]=391;
h_p[1073]=181;	n_p[1073]=519;
h_p[1074]=181;	n_p[1074]=623;
h_p[1075]=181;	n_p[1075]=653;
h_p[1076]=181;	n_p[1076]=673;
h_p[1077]=181;	n_p[1077]=701;
h_p[1078]=185;	n_p[1078]=2;
h_p[1079]=185;	n_p[1079]=6;
h_p[1080]=185;	n_p[1080]=10;
h_p[1081]=185;	n_p[1081]=18;
h_p[1082]=185;	n_p[1082]=26;
h_p[1083]=185;	n_p[1083]=40;
h_p[1084]=185;	n_p[1084]=46;
h_p[1085]=185;	n_p[1085]=78;
h_p[1086]=185;	n_p[1086]=230;
h_p[1087]=185;	n_p[1087]=542;
h_p[1088]=187;	n_p[1088]=1;
h_p[1089]=187;	n_p[1089]=17;
h_p[1090]=187;	n_p[1090]=21;
h_p[1091]=187;	n_p[1091]=53;
h_p[1092]=187;	n_p[1092]=253;
h_p[1093]=191;	n_p[1093]=226;
h_p[1094]=193;	n_p[1094]=3;
h_p[1095]=193;	n_p[1095]=15;
h_p[1096]=193;	n_p[1096]=27;
h_p[1097]=193;	n_p[1097]=63;
h_p[1098]=193;	n_p[1098]=87;		/* 193*2^87-1 is NOT prime */
h_p[1099]=193;	n_p[1099]=135;
h_p[1100]=193;	n_p[1100]=543;
h_p[1101]=197;	n_p[1101]=2;
h_p[1102]=197;	n_p[1102]=16;
h_p[1103]=197;	n_p[1103]=20;
h_p[1104]=197;	n_p[1104]=22;
h_p[1105]=197;	n_p[1105]=40;
h_p[1106]=197;	n_p[1106]=82;
h_p[1107]=197;	n_p[1107]=112;
h_p[1108]=197;	n_p[1108]=178;
h_p[1109]=197;	n_p[1109]=230;
h_p[1110]=197;	n_p[1110]=302;
h_p[1111]=197;	n_p[1111]=304;
h_p[1112]=197;	n_p[1112]=328;
h_p[1113]=197;	n_p[1113]=374;
h_p[1114]=197;	n_p[1114]=442;
h_p[1115]=197;	n_p[1115]=472;
h_p[1116]=197;	n_p[1116]=500;
h_p[1117]=197;	n_p[1117]=580;
h_p[1118]=197;	n_p[1118]=694;
h_p[1119]=199;	n_p[1119]=1;
h_p[1120]=199;	n_p[1120]=5;
h_p[1121]=199;	n_p[1121]=7;
h_p[1122]=199;	n_p[1122]=15;
h_p[1123]=199;	n_p[1123]=19;
h_p[1124]=199;	n_p[1124]=23;
h_p[1125]=199;	n_p[1125]=25;
h_p[1126]=199;	n_p[1126]=27;
h_p[1127]=199;	n_p[1127]=43;
h_p[1128]=199;	n_p[1128]=65;
h_p[1129]=199;	n_p[1129]=99;
h_p[1130]=199;	n_p[1130]=125;
h_p[1131]=199;	n_p[1131]=141;
h_p[1132]=199;	n_p[1132]=165;
h_p[1133]=199;	n_p[1133]=201;
h_p[1134]=199;	n_p[1134]=211;		/* 199*2^221-1 is NOT prime */
h_p[1135]=199;	n_p[1135]=331;
h_p[1136]=199;	n_p[1136]=369;
h_p[1137]=199;	n_p[1137]=389;
h_p[1138]=199;	n_p[1138]=445;
h_p[1139]=199;	n_p[1139]=461;
h_p[1140]=199;	n_p[1140]=463;
h_p[1141]=199;	n_p[1141]=467;
h_p[1142]=199;	n_p[1142]=513;
h_p[1143]=199;	n_p[1143]=583;
h_p[1144]=199;	n_p[1144]=835;

/*
 * lucas_chk - check the lucas function on known primes
 *
 * This function tests entries in the above h_p, n_p table
 * when n_p is below a given limit.
 *
 * input:
 *	high_n	skip tests on n_p[i] > high_n
 *
 * returns:
 *	1	all is ok
 *	0	something went wrong
 */
define
lucas_chk(high_n)
{
	local i;	/* index */
	local result;	/* 0 => non-prime, 1 => prime, -1 => bad test */
	local error;	/* number of errors and bad tests found */

	/*
	 * firewall
	 */
	if (!isint(high_n)) {
		ldebug("test_lucas", "high_n is non-int");
		quit "FATAL: bad args: high_n must be an integer";
	}

	/*
	 * scan thru the above prime table
	 */
	error = 0;
	for (i=0; i < prime_cnt; ++i) {

		/* skip primes where h>=2^n */
		if (highbit(h_p[i]) >= n_p[i]) {
			if (dbg != 0) {
				print "h>=2^n skip:", h_p[i]:"*2^":n_p[i]:"-1";
			}
			continue;
		}

		/* test the prime if it is small enough */
		if (n_p[i] <= high_n) {

			/* test the table value */
			result = lucas(h_p[i], n_p[i]);

			/* report the test */
			if (result == 0) {
				print "ERROR, bad primality test of",\
				    h_p[i]:"*2^":n_p[i]:"-1";
				++error;
			} else if (result == 1) {
				print h_p[i]:"*2^":n_p[i]:"-1 is prime";
			} else if (result == -1) {
				print "ERROR, failed to compute v(1) for",\
				    h_p[i]:"*2^":n_p[i]:"-1";
				++error;
			} else {
				print "ERROR, bogus return value:", result;
				++error;
			}
		}
	}

	/* return the full status */
	if (error == 0) {
		print "lucas_chk(":high_n:") passed";
		return 1;
	} else if (error == 1) {
		print "lucas_chk(":high_n:") failed", error, "test";
		return 0;
	} else {
		print "lucas_chk(":high_n:") failed", error, "tests";
		return 0;
	}
}

global lib_debug;
if (!isnum(lib_debug) || lib_debug>0) print "lucas_chk(high_n) defined";