1 /****************************************************************************
2 *
3 * Copyright (C) 2014-2021 Cisco and/or its affiliates. All rights reserved.
4 * Copyright (C) 2006-2013 Sourcefire, Inc.
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License Version 2 as
8 * published by the Free Software Foundation. You may not use, modify or
9 * distribute this program under any other version of the GNU General
10 * Public License.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 *
21 ****************************************************************************/
22
23 /*
24 * sfprimetable.c
25 *
26 * Prime number calculation via Table lookups.
27 *
28 * This was implemented for use with the hasing functions
29 * in sfghash, and sfxhash.
30 *
31 */
32 #ifdef HAVE_CONFIG_H
33 #include "config.h"
34 #endif
35
36 #include "sfprimetable.h"
37 /* 0-8K, increments=8 */
38 static
39 unsigned prime_table0[1024]={
40 3, /* 1 */
41 7, /* 9 */
42 17, /* 17 */
43 23, /* 25 */
44 31, /* 33 */
45 41, /* 41 */
46 47, /* 49 */
47 53, /* 57 */
48 61, /* 65 */
49 73, /* 73 */
50 79, /* 81 */
51 89, /* 89 */
52 97, /* 97 */
53 103, /* 105 */
54 113, /* 113 */
55 113, /* 121 */
56 127, /* 129 */
57 137, /* 137 */
58 139, /* 145 */
59 151, /* 153 */
60 157, /* 161 */
61 167, /* 169 */
62 173, /* 177 */
63 181, /* 185 */
64 193, /* 193 */
65 199, /* 201 */
66 199, /* 209 */
67 211, /* 217 */
68 223, /* 225 */
69 233, /* 233 */
70 241, /* 241 */
71 241, /* 249 */
72 257, /* 257 */
73 263, /* 265 */
74 271, /* 273 */
75 281, /* 281 */
76 283, /* 289 */
77 293, /* 297 */
78 293, /* 305 */
79 313, /* 313 */
80 317, /* 321 */
81 317, /* 329 */
82 337, /* 337 */
83 337, /* 345 */
84 353, /* 353 */
85 359, /* 361 */
86 367, /* 369 */
87 373, /* 377 */
88 383, /* 385 */
89 389, /* 393 */
90 401, /* 401 */
91 409, /* 409 */
92 409, /* 417 */
93 421, /* 425 */
94 433, /* 433 */
95 439, /* 441 */
96 449, /* 449 */
97 457, /* 457 */
98 463, /* 465 */
99 467, /* 473 */
100 479, /* 481 */
101 487, /* 489 */
102 491, /* 497 */
103 503, /* 505 */
104 509, /* 513 */
105 521, /* 521 */
106 523, /* 529 */
107 523, /* 537 */
108 541, /* 545 */
109 547, /* 553 */
110 557, /* 561 */
111 569, /* 569 */
112 577, /* 577 */
113 577, /* 585 */
114 593, /* 593 */
115 601, /* 601 */
116 607, /* 609 */
117 617, /* 617 */
118 619, /* 625 */
119 631, /* 633 */
120 641, /* 641 */
121 647, /* 649 */
122 653, /* 657 */
123 661, /* 665 */
124 673, /* 673 */
125 677, /* 681 */
126 683, /* 689 */
127 691, /* 697 */
128 701, /* 705 */
129 709, /* 713 */
130 719, /* 721 */
131 727, /* 729 */
132 733, /* 737 */
133 743, /* 745 */
134 751, /* 753 */
135 761, /* 761 */
136 769, /* 769 */
137 773, /* 777 */
138 773, /* 785 */
139 787, /* 793 */
140 797, /* 801 */
141 809, /* 809 */
142 811, /* 817 */
143 823, /* 825 */
144 829, /* 833 */
145 839, /* 841 */
146 839, /* 849 */
147 857, /* 857 */
148 863, /* 865 */
149 863, /* 873 */
150 881, /* 881 */
151 887, /* 889 */
152 887, /* 897 */
153 887, /* 905 */
154 911, /* 913 */
155 919, /* 921 */
156 929, /* 929 */
157 937, /* 937 */
158 941, /* 945 */
159 953, /* 953 */
160 953, /* 961 */
161 967, /* 969 */
162 977, /* 977 */
163 983, /* 985 */
164 991, /* 993 */
165 997, /* 1001 */
166 1009, /* 1009 */
167 1013, /* 1017 */
168 1021, /* 1025 */
169 1033, /* 1033 */
170 1039, /* 1041 */
171 1049, /* 1049 */
172 1051, /* 1057 */
173 1063, /* 1065 */
174 1069, /* 1073 */
175 1069, /* 1081 */
176 1087, /* 1089 */
177 1097, /* 1097 */
178 1103, /* 1105 */
179 1109, /* 1113 */
180 1117, /* 1121 */
181 1129, /* 1129 */
182 1129, /* 1137 */
183 1129, /* 1145 */
184 1153, /* 1153 */
185 1153, /* 1161 */
186 1163, /* 1169 */
187 1171, /* 1177 */
188 1181, /* 1185 */
189 1193, /* 1193 */
190 1201, /* 1201 */
191 1201, /* 1209 */
192 1217, /* 1217 */
193 1223, /* 1225 */
194 1231, /* 1233 */
195 1237, /* 1241 */
196 1249, /* 1249 */
197 1249, /* 1257 */
198 1259, /* 1265 */
199 1259, /* 1273 */
200 1279, /* 1281 */
201 1289, /* 1289 */
202 1297, /* 1297 */
203 1303, /* 1305 */
204 1307, /* 1313 */
205 1321, /* 1321 */
206 1327, /* 1329 */
207 1327, /* 1337 */
208 1327, /* 1345 */
209 1327, /* 1353 */
210 1361, /* 1361 */
211 1367, /* 1369 */
212 1373, /* 1377 */
213 1381, /* 1385 */
214 1381, /* 1393 */
215 1399, /* 1401 */
216 1409, /* 1409 */
217 1409, /* 1417 */
218 1423, /* 1425 */
219 1433, /* 1433 */
220 1439, /* 1441 */
221 1447, /* 1449 */
222 1453, /* 1457 */
223 1459, /* 1465 */
224 1471, /* 1473 */
225 1481, /* 1481 */
226 1489, /* 1489 */
227 1493, /* 1497 */
228 1499, /* 1505 */
229 1511, /* 1513 */
230 1511, /* 1521 */
231 1523, /* 1529 */
232 1531, /* 1537 */
233 1543, /* 1545 */
234 1553, /* 1553 */
235 1559, /* 1561 */
236 1567, /* 1569 */
237 1571, /* 1577 */
238 1583, /* 1585 */
239 1583, /* 1593 */
240 1601, /* 1601 */
241 1609, /* 1609 */
242 1613, /* 1617 */
243 1621, /* 1625 */
244 1627, /* 1633 */
245 1637, /* 1641 */
246 1637, /* 1649 */
247 1657, /* 1657 */
248 1663, /* 1665 */
249 1669, /* 1673 */
250 1669, /* 1681 */
251 1669, /* 1689 */
252 1697, /* 1697 */
253 1699, /* 1705 */
254 1709, /* 1713 */
255 1721, /* 1721 */
256 1723, /* 1729 */
257 1733, /* 1737 */
258 1741, /* 1745 */
259 1753, /* 1753 */
260 1759, /* 1761 */
261 1759, /* 1769 */
262 1777, /* 1777 */
263 1783, /* 1785 */
264 1789, /* 1793 */
265 1801, /* 1801 */
266 1801, /* 1809 */
267 1811, /* 1817 */
268 1823, /* 1825 */
269 1831, /* 1833 */
270 1831, /* 1841 */
271 1847, /* 1849 */
272 1847, /* 1857 */
273 1861, /* 1865 */
274 1873, /* 1873 */
275 1879, /* 1881 */
276 1889, /* 1889 */
277 1889, /* 1897 */
278 1901, /* 1905 */
279 1913, /* 1913 */
280 1913, /* 1921 */
281 1913, /* 1929 */
282 1933, /* 1937 */
283 1933, /* 1945 */
284 1951, /* 1953 */
285 1951, /* 1961 */
286 1951, /* 1969 */
287 1973, /* 1977 */
288 1979, /* 1985 */
289 1993, /* 1993 */
290 1999, /* 2001 */
291 2003, /* 2009 */
292 2017, /* 2017 */
293 2017, /* 2025 */
294 2029, /* 2033 */
295 2039, /* 2041 */
296 2039, /* 2049 */
297 2053, /* 2057 */
298 2063, /* 2065 */
299 2069, /* 2073 */
300 2081, /* 2081 */
301 2089, /* 2089 */
302 2089, /* 2097 */
303 2099, /* 2105 */
304 2113, /* 2113 */
305 2113, /* 2121 */
306 2129, /* 2129 */
307 2137, /* 2137 */
308 2143, /* 2145 */
309 2153, /* 2153 */
310 2161, /* 2161 */
311 2161, /* 2169 */
312 2161, /* 2177 */
313 2179, /* 2185 */
314 2179, /* 2193 */
315 2179, /* 2201 */
316 2207, /* 2209 */
317 2213, /* 2217 */
318 2221, /* 2225 */
319 2221, /* 2233 */
320 2239, /* 2241 */
321 2243, /* 2249 */
322 2251, /* 2257 */
323 2251, /* 2265 */
324 2273, /* 2273 */
325 2281, /* 2281 */
326 2287, /* 2289 */
327 2297, /* 2297 */
328 2297, /* 2305 */
329 2311, /* 2313 */
330 2311, /* 2321 */
331 2311, /* 2329 */
332 2333, /* 2337 */
333 2341, /* 2345 */
334 2351, /* 2353 */
335 2357, /* 2361 */
336 2357, /* 2369 */
337 2377, /* 2377 */
338 2383, /* 2385 */
339 2393, /* 2393 */
340 2399, /* 2401 */
341 2399, /* 2409 */
342 2417, /* 2417 */
343 2423, /* 2425 */
344 2423, /* 2433 */
345 2441, /* 2441 */
346 2447, /* 2449 */
347 2447, /* 2457 */
348 2459, /* 2465 */
349 2473, /* 2473 */
350 2477, /* 2481 */
351 2477, /* 2489 */
352 2477, /* 2497 */
353 2503, /* 2505 */
354 2503, /* 2513 */
355 2521, /* 2521 */
356 2521, /* 2529 */
357 2531, /* 2537 */
358 2543, /* 2545 */
359 2551, /* 2553 */
360 2557, /* 2561 */
361 2557, /* 2569 */
362 2557, /* 2577 */
363 2579, /* 2585 */
364 2593, /* 2593 */
365 2593, /* 2601 */
366 2609, /* 2609 */
367 2617, /* 2617 */
368 2621, /* 2625 */
369 2633, /* 2633 */
370 2633, /* 2641 */
371 2647, /* 2649 */
372 2657, /* 2657 */
373 2663, /* 2665 */
374 2671, /* 2673 */
375 2677, /* 2681 */
376 2689, /* 2689 */
377 2693, /* 2697 */
378 2699, /* 2705 */
379 2713, /* 2713 */
380 2719, /* 2721 */
381 2729, /* 2729 */
382 2731, /* 2737 */
383 2741, /* 2745 */
384 2753, /* 2753 */
385 2753, /* 2761 */
386 2767, /* 2769 */
387 2777, /* 2777 */
388 2777, /* 2785 */
389 2791, /* 2793 */
390 2801, /* 2801 */
391 2803, /* 2809 */
392 2803, /* 2817 */
393 2819, /* 2825 */
394 2833, /* 2833 */
395 2837, /* 2841 */
396 2843, /* 2849 */
397 2857, /* 2857 */
398 2861, /* 2865 */
399 2861, /* 2873 */
400 2879, /* 2881 */
401 2887, /* 2889 */
402 2897, /* 2897 */
403 2903, /* 2905 */
404 2909, /* 2913 */
405 2917, /* 2921 */
406 2927, /* 2929 */
407 2927, /* 2937 */
408 2939, /* 2945 */
409 2953, /* 2953 */
410 2957, /* 2961 */
411 2969, /* 2969 */
412 2971, /* 2977 */
413 2971, /* 2985 */
414 2971, /* 2993 */
415 3001, /* 3001 */
416 3001, /* 3009 */
417 3011, /* 3017 */
418 3023, /* 3025 */
419 3023, /* 3033 */
420 3041, /* 3041 */
421 3049, /* 3049 */
422 3049, /* 3057 */
423 3061, /* 3065 */
424 3067, /* 3073 */
425 3079, /* 3081 */
426 3089, /* 3089 */
427 3089, /* 3097 */
428 3089, /* 3105 */
429 3109, /* 3113 */
430 3121, /* 3121 */
431 3121, /* 3129 */
432 3137, /* 3137 */
433 3137, /* 3145 */
434 3137, /* 3153 */
435 3137, /* 3161 */
436 3169, /* 3169 */
437 3169, /* 3177 */
438 3181, /* 3185 */
439 3191, /* 3193 */
440 3191, /* 3201 */
441 3209, /* 3209 */
442 3217, /* 3217 */
443 3221, /* 3225 */
444 3229, /* 3233 */
445 3229, /* 3241 */
446 3229, /* 3249 */
447 3257, /* 3257 */
448 3259, /* 3265 */
449 3271, /* 3273 */
450 3271, /* 3281 */
451 3271, /* 3289 */
452 3271, /* 3297 */
453 3301, /* 3305 */
454 3313, /* 3313 */
455 3319, /* 3321 */
456 3329, /* 3329 */
457 3331, /* 3337 */
458 3343, /* 3345 */
459 3347, /* 3353 */
460 3361, /* 3361 */
461 3361, /* 3369 */
462 3373, /* 3377 */
463 3373, /* 3385 */
464 3391, /* 3393 */
465 3391, /* 3401 */
466 3407, /* 3409 */
467 3413, /* 3417 */
468 3413, /* 3425 */
469 3433, /* 3433 */
470 3433, /* 3441 */
471 3449, /* 3449 */
472 3457, /* 3457 */
473 3463, /* 3465 */
474 3469, /* 3473 */
475 3469, /* 3481 */
476 3469, /* 3489 */
477 3491, /* 3497 */
478 3499, /* 3505 */
479 3511, /* 3513 */
480 3517, /* 3521 */
481 3529, /* 3529 */
482 3533, /* 3537 */
483 3541, /* 3545 */
484 3547, /* 3553 */
485 3559, /* 3561 */
486 3559, /* 3569 */
487 3571, /* 3577 */
488 3583, /* 3585 */
489 3593, /* 3593 */
490 3593, /* 3601 */
491 3607, /* 3609 */
492 3617, /* 3617 */
493 3623, /* 3625 */
494 3631, /* 3633 */
495 3637, /* 3641 */
496 3643, /* 3649 */
497 3643, /* 3657 */
498 3659, /* 3665 */
499 3673, /* 3673 */
500 3677, /* 3681 */
501 3677, /* 3689 */
502 3697, /* 3697 */
503 3701, /* 3705 */
504 3709, /* 3713 */
505 3719, /* 3721 */
506 3727, /* 3729 */
507 3733, /* 3737 */
508 3739, /* 3745 */
509 3739, /* 3753 */
510 3761, /* 3761 */
511 3769, /* 3769 */
512 3769, /* 3777 */
513 3779, /* 3785 */
514 3793, /* 3793 */
515 3797, /* 3801 */
516 3803, /* 3809 */
517 3803, /* 3817 */
518 3823, /* 3825 */
519 3833, /* 3833 */
520 3833, /* 3841 */
521 3847, /* 3849 */
522 3853, /* 3857 */
523 3863, /* 3865 */
524 3863, /* 3873 */
525 3881, /* 3881 */
526 3889, /* 3889 */
527 3889, /* 3897 */
528 3889, /* 3905 */
529 3911, /* 3913 */
530 3919, /* 3921 */
531 3929, /* 3929 */
532 3931, /* 3937 */
533 3943, /* 3945 */
534 3947, /* 3953 */
535 3947, /* 3961 */
536 3967, /* 3969 */
537 3967, /* 3977 */
538 3967, /* 3985 */
539 3989, /* 3993 */
540 4001, /* 4001 */
541 4007, /* 4009 */
542 4013, /* 4017 */
543 4021, /* 4025 */
544 4027, /* 4033 */
545 4027, /* 4041 */
546 4049, /* 4049 */
547 4057, /* 4057 */
548 4057, /* 4065 */
549 4073, /* 4073 */
550 4079, /* 4081 */
551 4079, /* 4089 */
552 4093, /* 4097 */
553 4099, /* 4105 */
554 4111, /* 4113 */
555 4111, /* 4121 */
556 4129, /* 4129 */
557 4133, /* 4137 */
558 4139, /* 4145 */
559 4153, /* 4153 */
560 4159, /* 4161 */
561 4159, /* 4169 */
562 4177, /* 4177 */
563 4177, /* 4185 */
564 4177, /* 4193 */
565 4201, /* 4201 */
566 4201, /* 4209 */
567 4217, /* 4217 */
568 4219, /* 4225 */
569 4231, /* 4233 */
570 4241, /* 4241 */
571 4243, /* 4249 */
572 4253, /* 4257 */
573 4261, /* 4265 */
574 4273, /* 4273 */
575 4273, /* 4281 */
576 4289, /* 4289 */
577 4297, /* 4297 */
578 4297, /* 4305 */
579 4297, /* 4313 */
580 4297, /* 4321 */
581 4327, /* 4329 */
582 4337, /* 4337 */
583 4339, /* 4345 */
584 4349, /* 4353 */
585 4357, /* 4361 */
586 4363, /* 4369 */
587 4373, /* 4377 */
588 4373, /* 4385 */
589 4391, /* 4393 */
590 4397, /* 4401 */
591 4409, /* 4409 */
592 4409, /* 4417 */
593 4423, /* 4425 */
594 4423, /* 4433 */
595 4441, /* 4441 */
596 4447, /* 4449 */
597 4457, /* 4457 */
598 4463, /* 4465 */
599 4463, /* 4473 */
600 4481, /* 4481 */
601 4483, /* 4489 */
602 4493, /* 4497 */
603 4493, /* 4505 */
604 4513, /* 4513 */
605 4519, /* 4521 */
606 4523, /* 4529 */
607 4523, /* 4537 */
608 4523, /* 4545 */
609 4549, /* 4553 */
610 4561, /* 4561 */
611 4567, /* 4569 */
612 4567, /* 4577 */
613 4583, /* 4585 */
614 4591, /* 4593 */
615 4597, /* 4601 */
616 4603, /* 4609 */
617 4603, /* 4617 */
618 4621, /* 4625 */
619 4621, /* 4633 */
620 4639, /* 4641 */
621 4649, /* 4649 */
622 4657, /* 4657 */
623 4663, /* 4665 */
624 4673, /* 4673 */
625 4679, /* 4681 */
626 4679, /* 4689 */
627 4691, /* 4697 */
628 4703, /* 4705 */
629 4703, /* 4713 */
630 4721, /* 4721 */
631 4729, /* 4729 */
632 4733, /* 4737 */
633 4733, /* 4745 */
634 4751, /* 4753 */
635 4759, /* 4761 */
636 4759, /* 4769 */
637 4759, /* 4777 */
638 4783, /* 4785 */
639 4793, /* 4793 */
640 4801, /* 4801 */
641 4801, /* 4809 */
642 4817, /* 4817 */
643 4817, /* 4825 */
644 4831, /* 4833 */
645 4831, /* 4841 */
646 4831, /* 4849 */
647 4831, /* 4857 */
648 4861, /* 4865 */
649 4871, /* 4873 */
650 4877, /* 4881 */
651 4889, /* 4889 */
652 4889, /* 4897 */
653 4903, /* 4905 */
654 4909, /* 4913 */
655 4919, /* 4921 */
656 4919, /* 4929 */
657 4937, /* 4937 */
658 4943, /* 4945 */
659 4951, /* 4953 */
660 4957, /* 4961 */
661 4969, /* 4969 */
662 4973, /* 4977 */
663 4973, /* 4985 */
664 4993, /* 4993 */
665 4999, /* 5001 */
666 5009, /* 5009 */
667 5011, /* 5017 */
668 5023, /* 5025 */
669 5023, /* 5033 */
670 5039, /* 5041 */
671 5039, /* 5049 */
672 5051, /* 5057 */
673 5059, /* 5065 */
674 5059, /* 5073 */
675 5081, /* 5081 */
676 5087, /* 5089 */
677 5087, /* 5097 */
678 5101, /* 5105 */
679 5113, /* 5113 */
680 5119, /* 5121 */
681 5119, /* 5129 */
682 5119, /* 5137 */
683 5119, /* 5145 */
684 5153, /* 5153 */
685 5153, /* 5161 */
686 5167, /* 5169 */
687 5171, /* 5177 */
688 5179, /* 5185 */
689 5189, /* 5193 */
690 5197, /* 5201 */
691 5209, /* 5209 */
692 5209, /* 5217 */
693 5209, /* 5225 */
694 5233, /* 5233 */
695 5237, /* 5241 */
696 5237, /* 5249 */
697 5237, /* 5257 */
698 5261, /* 5265 */
699 5273, /* 5273 */
700 5281, /* 5281 */
701 5281, /* 5289 */
702 5297, /* 5297 */
703 5303, /* 5305 */
704 5309, /* 5313 */
705 5309, /* 5321 */
706 5323, /* 5329 */
707 5333, /* 5337 */
708 5333, /* 5345 */
709 5351, /* 5353 */
710 5351, /* 5361 */
711 5351, /* 5369 */
712 5351, /* 5377 */
713 5381, /* 5385 */
714 5393, /* 5393 */
715 5399, /* 5401 */
716 5407, /* 5409 */
717 5417, /* 5417 */
718 5419, /* 5425 */
719 5431, /* 5433 */
720 5441, /* 5441 */
721 5449, /* 5449 */
722 5449, /* 5457 */
723 5449, /* 5465 */
724 5471, /* 5473 */
725 5479, /* 5481 */
726 5483, /* 5489 */
727 5483, /* 5497 */
728 5503, /* 5505 */
729 5507, /* 5513 */
730 5521, /* 5521 */
731 5527, /* 5529 */
732 5531, /* 5537 */
733 5531, /* 5545 */
734 5531, /* 5553 */
735 5557, /* 5561 */
736 5569, /* 5569 */
737 5573, /* 5577 */
738 5581, /* 5585 */
739 5591, /* 5593 */
740 5591, /* 5601 */
741 5591, /* 5609 */
742 5591, /* 5617 */
743 5623, /* 5625 */
744 5623, /* 5633 */
745 5641, /* 5641 */
746 5647, /* 5649 */
747 5657, /* 5657 */
748 5659, /* 5665 */
749 5669, /* 5673 */
750 5669, /* 5681 */
751 5689, /* 5689 */
752 5693, /* 5697 */
753 5701, /* 5705 */
754 5711, /* 5713 */
755 5717, /* 5721 */
756 5717, /* 5729 */
757 5737, /* 5737 */
758 5743, /* 5745 */
759 5749, /* 5753 */
760 5749, /* 5761 */
761 5749, /* 5769 */
762 5749, /* 5777 */
763 5783, /* 5785 */
764 5791, /* 5793 */
765 5801, /* 5801 */
766 5807, /* 5809 */
767 5813, /* 5817 */
768 5821, /* 5825 */
769 5827, /* 5833 */
770 5839, /* 5841 */
771 5849, /* 5849 */
772 5857, /* 5857 */
773 5861, /* 5865 */
774 5869, /* 5873 */
775 5881, /* 5881 */
776 5881, /* 5889 */
777 5897, /* 5897 */
778 5903, /* 5905 */
779 5903, /* 5913 */
780 5903, /* 5921 */
781 5927, /* 5929 */
782 5927, /* 5937 */
783 5939, /* 5945 */
784 5953, /* 5953 */
785 5953, /* 5961 */
786 5953, /* 5969 */
787 5953, /* 5977 */
788 5981, /* 5985 */
789 5987, /* 5993 */
790 5987, /* 6001 */
791 6007, /* 6009 */
792 6011, /* 6017 */
793 6011, /* 6025 */
794 6029, /* 6033 */
795 6037, /* 6041 */
796 6047, /* 6049 */
797 6053, /* 6057 */
798 6053, /* 6065 */
799 6073, /* 6073 */
800 6079, /* 6081 */
801 6089, /* 6089 */
802 6091, /* 6097 */
803 6101, /* 6105 */
804 6113, /* 6113 */
805 6121, /* 6121 */
806 6121, /* 6129 */
807 6133, /* 6137 */
808 6143, /* 6145 */
809 6151, /* 6153 */
810 6151, /* 6161 */
811 6163, /* 6169 */
812 6173, /* 6177 */
813 6173, /* 6185 */
814 6173, /* 6193 */
815 6199, /* 6201 */
816 6203, /* 6209 */
817 6217, /* 6217 */
818 6221, /* 6225 */
819 6229, /* 6233 */
820 6229, /* 6241 */
821 6247, /* 6249 */
822 6257, /* 6257 */
823 6263, /* 6265 */
824 6271, /* 6273 */
825 6277, /* 6281 */
826 6287, /* 6289 */
827 6287, /* 6297 */
828 6301, /* 6305 */
829 6311, /* 6313 */
830 6317, /* 6321 */
831 6329, /* 6329 */
832 6337, /* 6337 */
833 6343, /* 6345 */
834 6353, /* 6353 */
835 6361, /* 6361 */
836 6367, /* 6369 */
837 6373, /* 6377 */
838 6379, /* 6385 */
839 6389, /* 6393 */
840 6397, /* 6401 */
841 6397, /* 6409 */
842 6397, /* 6417 */
843 6421, /* 6425 */
844 6427, /* 6433 */
845 6427, /* 6441 */
846 6449, /* 6449 */
847 6451, /* 6457 */
848 6451, /* 6465 */
849 6473, /* 6473 */
850 6481, /* 6481 */
851 6481, /* 6489 */
852 6491, /* 6497 */
853 6491, /* 6505 */
854 6491, /* 6513 */
855 6521, /* 6521 */
856 6529, /* 6529 */
857 6529, /* 6537 */
858 6529, /* 6545 */
859 6553, /* 6553 */
860 6553, /* 6561 */
861 6569, /* 6569 */
862 6577, /* 6577 */
863 6581, /* 6585 */
864 6581, /* 6593 */
865 6599, /* 6601 */
866 6607, /* 6609 */
867 6607, /* 6617 */
868 6619, /* 6625 */
869 6619, /* 6633 */
870 6637, /* 6641 */
871 6637, /* 6649 */
872 6653, /* 6657 */
873 6661, /* 6665 */
874 6673, /* 6673 */
875 6679, /* 6681 */
876 6689, /* 6689 */
877 6691, /* 6697 */
878 6703, /* 6705 */
879 6709, /* 6713 */
880 6719, /* 6721 */
881 6719, /* 6729 */
882 6737, /* 6737 */
883 6737, /* 6745 */
884 6737, /* 6753 */
885 6761, /* 6761 */
886 6763, /* 6769 */
887 6763, /* 6777 */
888 6781, /* 6785 */
889 6793, /* 6793 */
890 6793, /* 6801 */
891 6803, /* 6809 */
892 6803, /* 6817 */
893 6823, /* 6825 */
894 6833, /* 6833 */
895 6841, /* 6841 */
896 6841, /* 6849 */
897 6857, /* 6857 */
898 6863, /* 6865 */
899 6871, /* 6873 */
900 6871, /* 6881 */
901 6883, /* 6889 */
902 6883, /* 6897 */
903 6899, /* 6905 */
904 6911, /* 6913 */
905 6917, /* 6921 */
906 6917, /* 6929 */
907 6917, /* 6937 */
908 6917, /* 6945 */
909 6949, /* 6953 */
910 6961, /* 6961 */
911 6967, /* 6969 */
912 6977, /* 6977 */
913 6983, /* 6985 */
914 6991, /* 6993 */
915 7001, /* 7001 */
916 7001, /* 7009 */
917 7013, /* 7017 */
918 7019, /* 7025 */
919 7027, /* 7033 */
920 7039, /* 7041 */
921 7043, /* 7049 */
922 7057, /* 7057 */
923 7057, /* 7065 */
924 7069, /* 7073 */
925 7079, /* 7081 */
926 7079, /* 7089 */
927 7079, /* 7097 */
928 7103, /* 7105 */
929 7109, /* 7113 */
930 7121, /* 7121 */
931 7129, /* 7129 */
932 7129, /* 7137 */
933 7129, /* 7145 */
934 7151, /* 7153 */
935 7159, /* 7161 */
936 7159, /* 7169 */
937 7177, /* 7177 */
938 7177, /* 7185 */
939 7193, /* 7193 */
940 7193, /* 7201 */
941 7207, /* 7209 */
942 7213, /* 7217 */
943 7219, /* 7225 */
944 7229, /* 7233 */
945 7237, /* 7241 */
946 7247, /* 7249 */
947 7253, /* 7257 */
948 7253, /* 7265 */
949 7253, /* 7273 */
950 7253, /* 7281 */
951 7283, /* 7289 */
952 7297, /* 7297 */
953 7297, /* 7305 */
954 7309, /* 7313 */
955 7321, /* 7321 */
956 7321, /* 7329 */
957 7333, /* 7337 */
958 7333, /* 7345 */
959 7351, /* 7353 */
960 7351, /* 7361 */
961 7369, /* 7369 */
962 7369, /* 7377 */
963 7369, /* 7385 */
964 7393, /* 7393 */
965 7393, /* 7401 */
966 7393, /* 7409 */
967 7417, /* 7417 */
968 7417, /* 7425 */
969 7433, /* 7433 */
970 7433, /* 7441 */
971 7433, /* 7449 */
972 7457, /* 7457 */
973 7459, /* 7465 */
974 7459, /* 7473 */
975 7481, /* 7481 */
976 7489, /* 7489 */
977 7489, /* 7497 */
978 7499, /* 7505 */
979 7507, /* 7513 */
980 7517, /* 7521 */
981 7529, /* 7529 */
982 7537, /* 7537 */
983 7541, /* 7545 */
984 7549, /* 7553 */
985 7561, /* 7561 */
986 7561, /* 7569 */
987 7577, /* 7577 */
988 7583, /* 7585 */
989 7591, /* 7593 */
990 7591, /* 7601 */
991 7607, /* 7609 */
992 7607, /* 7617 */
993 7621, /* 7625 */
994 7621, /* 7633 */
995 7639, /* 7641 */
996 7649, /* 7649 */
997 7649, /* 7657 */
998 7649, /* 7665 */
999 7673, /* 7673 */
1000 7681, /* 7681 */
1001 7687, /* 7689 */
1002 7691, /* 7697 */
1003 7703, /* 7705 */
1004 7703, /* 7713 */
1005 7717, /* 7721 */
1006 7727, /* 7729 */
1007 7727, /* 7737 */
1008 7741, /* 7745 */
1009 7753, /* 7753 */
1010 7759, /* 7761 */
1011 7759, /* 7769 */
1012 7759, /* 7777 */
1013 7759, /* 7785 */
1014 7793, /* 7793 */
1015 7793, /* 7801 */
1016 7793, /* 7809 */
1017 7817, /* 7817 */
1018 7823, /* 7825 */
1019 7829, /* 7833 */
1020 7841, /* 7841 */
1021 7841, /* 7849 */
1022 7853, /* 7857 */
1023 7853, /* 7865 */
1024 7873, /* 7873 */
1025 7879, /* 7881 */
1026 7883, /* 7889 */
1027 7883, /* 7897 */
1028 7901, /* 7905 */
1029 7907, /* 7913 */
1030 7919, /* 7921 */
1031 7927, /* 7929 */
1032 7937, /* 7937 */
1033 7937, /* 7945 */
1034 7951, /* 7953 */
1035 7951, /* 7961 */
1036 7963, /* 7969 */
1037 7963, /* 7977 */
1038 7963, /* 7985 */
1039 7993, /* 7993 */
1040 7993, /* 8001 */
1041 8009, /* 8009 */
1042 8017, /* 8017 */
1043 8017, /* 8025 */
1044 8017, /* 8033 */
1045 8039, /* 8041 */
1046 8039, /* 8049 */
1047 8053, /* 8057 */
1048 8059, /* 8065 */
1049 8069, /* 8073 */
1050 8081, /* 8081 */
1051 8089, /* 8089 */
1052 8093, /* 8097 */
1053 8101, /* 8105 */
1054 8111, /* 8113 */
1055 8117, /* 8121 */
1056 8123, /* 8129 */
1057 8123, /* 8137 */
1058 8123, /* 8145 */
1059 8147, /* 8153 */
1060 8161, /* 8161 */
1061 8167, /* 8169 */
1062 8171, /* 8177 */
1063 8179, /* 8185 */
1064 };
1065 /* 0-64K, increments=64 */
1066 static
1067 unsigned prime_table1[]={
1068 1, /* 1 */
1069 61, /* 65 */
1070 127, /* 129 */
1071 193, /* 193 */
1072 257, /* 257 */
1073 317, /* 321 */
1074 383, /* 385 */
1075 449, /* 449 */
1076 509, /* 513 */
1077 577, /* 577 */
1078 641, /* 641 */
1079 701, /* 705 */
1080 769, /* 769 */
1081 829, /* 833 */
1082 887, /* 897 */
1083 953, /* 961 */
1084 1021, /* 1025 */
1085 1087, /* 1089 */
1086 1153, /* 1153 */
1087 1217, /* 1217 */
1088 1279, /* 1281 */
1089 1327, /* 1345 */
1090 1409, /* 1409 */
1091 1471, /* 1473 */
1092 1531, /* 1537 */
1093 1601, /* 1601 */
1094 1663, /* 1665 */
1095 1723, /* 1729 */
1096 1789, /* 1793 */
1097 1847, /* 1857 */
1098 1913, /* 1921 */
1099 1979, /* 1985 */
1100 2039, /* 2049 */
1101 2113, /* 2113 */
1102 2161, /* 2177 */
1103 2239, /* 2241 */
1104 2297, /* 2305 */
1105 2357, /* 2369 */
1106 2423, /* 2433 */
1107 2477, /* 2497 */
1108 2557, /* 2561 */
1109 2621, /* 2625 */
1110 2689, /* 2689 */
1111 2753, /* 2753 */
1112 2803, /* 2817 */
1113 2879, /* 2881 */
1114 2939, /* 2945 */
1115 3001, /* 3009 */
1116 3067, /* 3073 */
1117 3137, /* 3137 */
1118 3191, /* 3201 */
1119 3259, /* 3265 */
1120 3329, /* 3329 */
1121 3391, /* 3393 */
1122 3457, /* 3457 */
1123 3517, /* 3521 */
1124 3583, /* 3585 */
1125 3643, /* 3649 */
1126 3709, /* 3713 */
1127 3769, /* 3777 */
1128 3833, /* 3841 */
1129 3889, /* 3905 */
1130 3967, /* 3969 */
1131 4027, /* 4033 */
1132 4093, /* 4097 */
1133 4159, /* 4161 */
1134 4219, /* 4225 */
1135 4289, /* 4289 */
1136 4349, /* 4353 */
1137 4409, /* 4417 */
1138 4481, /* 4481 */
1139 4523, /* 4545 */
1140 4603, /* 4609 */
1141 4673, /* 4673 */
1142 4733, /* 4737 */
1143 4801, /* 4801 */
1144 4861, /* 4865 */
1145 4919, /* 4929 */
1146 4993, /* 4993 */
1147 5051, /* 5057 */
1148 5119, /* 5121 */
1149 5179, /* 5185 */
1150 5237, /* 5249 */
1151 5309, /* 5313 */
1152 5351, /* 5377 */
1153 5441, /* 5441 */
1154 5503, /* 5505 */
1155 5569, /* 5569 */
1156 5623, /* 5633 */
1157 5693, /* 5697 */
1158 5749, /* 5761 */
1159 5821, /* 5825 */
1160 5881, /* 5889 */
1161 5953, /* 5953 */
1162 6011, /* 6017 */
1163 6079, /* 6081 */
1164 6143, /* 6145 */
1165 6203, /* 6209 */
1166 6271, /* 6273 */
1167 6337, /* 6337 */
1168 6397, /* 6401 */
1169 6451, /* 6465 */
1170 6529, /* 6529 */
1171 6581, /* 6593 */
1172 6653, /* 6657 */
1173 6719, /* 6721 */
1174 6781, /* 6785 */
1175 6841, /* 6849 */
1176 6911, /* 6913 */
1177 6977, /* 6977 */
1178 7039, /* 7041 */
1179 7103, /* 7105 */
1180 7159, /* 7169 */
1181 7229, /* 7233 */
1182 7297, /* 7297 */
1183 7351, /* 7361 */
1184 7417, /* 7425 */
1185 7489, /* 7489 */
1186 7549, /* 7553 */
1187 7607, /* 7617 */
1188 7681, /* 7681 */
1189 7741, /* 7745 */
1190 7793, /* 7809 */
1191 7873, /* 7873 */
1192 7937, /* 7937 */
1193 7993, /* 8001 */
1194 8059, /* 8065 */
1195 8123, /* 8129 */
1196 8191, /* 8193 */
1197 8243, /* 8257 */
1198 8317, /* 8321 */
1199 8377, /* 8385 */
1200 8447, /* 8449 */
1201 8513, /* 8513 */
1202 8573, /* 8577 */
1203 8641, /* 8641 */
1204 8699, /* 8705 */
1205 8761, /* 8769 */
1206 8831, /* 8833 */
1207 8893, /* 8897 */
1208 8951, /* 8961 */
1209 9013, /* 9025 */
1210 9067, /* 9089 */
1211 9151, /* 9153 */
1212 9209, /* 9217 */
1213 9281, /* 9281 */
1214 9343, /* 9345 */
1215 9403, /* 9409 */
1216 9473, /* 9473 */
1217 9533, /* 9537 */
1218 9601, /* 9601 */
1219 9661, /* 9665 */
1220 9721, /* 9729 */
1221 9791, /* 9793 */
1222 9857, /* 9857 */
1223 9907, /* 9921 */
1224 9973, /* 9985 */
1225 10039, /* 10049 */
1226 10111, /* 10113 */
1227 10177, /* 10177 */
1228 10223, /* 10241 */
1229 10303, /* 10305 */
1230 10369, /* 10369 */
1231 10433, /* 10433 */
1232 10487, /* 10497 */
1233 10559, /* 10561 */
1234 10613, /* 10625 */
1235 10687, /* 10689 */
1236 10753, /* 10753 */
1237 10799, /* 10817 */
1238 10867, /* 10881 */
1239 10939, /* 10945 */
1240 11003, /* 11009 */
1241 11071, /* 11073 */
1242 11131, /* 11137 */
1243 11197, /* 11201 */
1244 11261, /* 11265 */
1245 11329, /* 11329 */
1246 11393, /* 11393 */
1247 11447, /* 11457 */
1248 11519, /* 11521 */
1249 11579, /* 11585 */
1250 11633, /* 11649 */
1251 11701, /* 11713 */
1252 11777, /* 11777 */
1253 11839, /* 11841 */
1254 11903, /* 11905 */
1255 11969, /* 11969 */
1256 12011, /* 12033 */
1257 12097, /* 12097 */
1258 12161, /* 12161 */
1259 12211, /* 12225 */
1260 12289, /* 12289 */
1261 12347, /* 12353 */
1262 12413, /* 12417 */
1263 12479, /* 12481 */
1264 12541, /* 12545 */
1265 12601, /* 12609 */
1266 12671, /* 12673 */
1267 12721, /* 12737 */
1268 12799, /* 12801 */
1269 12853, /* 12865 */
1270 12923, /* 12929 */
1271 12983, /* 12993 */
1272 13049, /* 13057 */
1273 13121, /* 13121 */
1274 13183, /* 13185 */
1275 13249, /* 13249 */
1276 13313, /* 13313 */
1277 13367, /* 13377 */
1278 13441, /* 13441 */
1279 13499, /* 13505 */
1280 13567, /* 13569 */
1281 13633, /* 13633 */
1282 13697, /* 13697 */
1283 13759, /* 13761 */
1284 13807, /* 13825 */
1285 13883, /* 13889 */
1286 13933, /* 13953 */
1287 14011, /* 14017 */
1288 14081, /* 14081 */
1289 14143, /* 14145 */
1290 14207, /* 14209 */
1291 14251, /* 14273 */
1292 14327, /* 14337 */
1293 14401, /* 14401 */
1294 14461, /* 14465 */
1295 14519, /* 14529 */
1296 14593, /* 14593 */
1297 14657, /* 14657 */
1298 14717, /* 14721 */
1299 14783, /* 14785 */
1300 14843, /* 14849 */
1301 14897, /* 14913 */
1302 14969, /* 14977 */
1303 15031, /* 15041 */
1304 15101, /* 15105 */
1305 15161, /* 15169 */
1306 15233, /* 15233 */
1307 15289, /* 15297 */
1308 15361, /* 15361 */
1309 15413, /* 15425 */
1310 15473, /* 15489 */
1311 15551, /* 15553 */
1312 15607, /* 15617 */
1313 15679, /* 15681 */
1314 15739, /* 15745 */
1315 15809, /* 15809 */
1316 15859, /* 15873 */
1317 15937, /* 15937 */
1318 16001, /* 16001 */
1319 16063, /* 16065 */
1320 16127, /* 16129 */
1321 16193, /* 16193 */
1322 16253, /* 16257 */
1323 16319, /* 16321 */
1324 16381, /* 16385 */
1325 16447, /* 16449 */
1326 16493, /* 16513 */
1327 16573, /* 16577 */
1328 16633, /* 16641 */
1329 16703, /* 16705 */
1330 16763, /* 16769 */
1331 16831, /* 16833 */
1332 16889, /* 16897 */
1333 16943, /* 16961 */
1334 17021, /* 17025 */
1335 17077, /* 17089 */
1336 17137, /* 17153 */
1337 17209, /* 17217 */
1338 17257, /* 17281 */
1339 17341, /* 17345 */
1340 17401, /* 17409 */
1341 17471, /* 17473 */
1342 17519, /* 17537 */
1343 17599, /* 17601 */
1344 17659, /* 17665 */
1345 17729, /* 17729 */
1346 17791, /* 17793 */
1347 17851, /* 17857 */
1348 17921, /* 17921 */
1349 17981, /* 17985 */
1350 18049, /* 18049 */
1351 18097, /* 18113 */
1352 18169, /* 18177 */
1353 18233, /* 18241 */
1354 18301, /* 18305 */
1355 18367, /* 18369 */
1356 18433, /* 18433 */
1357 18493, /* 18497 */
1358 18553, /* 18561 */
1359 18617, /* 18625 */
1360 18679, /* 18689 */
1361 18749, /* 18753 */
1362 18803, /* 18817 */
1363 18869, /* 18881 */
1364 18919, /* 18945 */
1365 19009, /* 19009 */
1366 19073, /* 19073 */
1367 19121, /* 19137 */
1368 19183, /* 19201 */
1369 19259, /* 19265 */
1370 19319, /* 19329 */
1371 19391, /* 19393 */
1372 19457, /* 19457 */
1373 19507, /* 19521 */
1374 19583, /* 19585 */
1375 19609, /* 19649 */
1376 19709, /* 19713 */
1377 19777, /* 19777 */
1378 19841, /* 19841 */
1379 19891, /* 19905 */
1380 19963, /* 19969 */
1381 20029, /* 20033 */
1382 20089, /* 20097 */
1383 20161, /* 20161 */
1384 20219, /* 20225 */
1385 20287, /* 20289 */
1386 20353, /* 20353 */
1387 20411, /* 20417 */
1388 20479, /* 20481 */
1389 20543, /* 20545 */
1390 20599, /* 20609 */
1391 20663, /* 20673 */
1392 20731, /* 20737 */
1393 20789, /* 20801 */
1394 20857, /* 20865 */
1395 20929, /* 20929 */
1396 20983, /* 20993 */
1397 21031, /* 21057 */
1398 21121, /* 21121 */
1399 21179, /* 21185 */
1400 21247, /* 21249 */
1401 21313, /* 21313 */
1402 21377, /* 21377 */
1403 21433, /* 21441 */
1404 21503, /* 21505 */
1405 21569, /* 21569 */
1406 21617, /* 21633 */
1407 21683, /* 21697 */
1408 21757, /* 21761 */
1409 21821, /* 21825 */
1410 21881, /* 21889 */
1411 21943, /* 21953 */
1412 22013, /* 22017 */
1413 22079, /* 22081 */
1414 22133, /* 22145 */
1415 22193, /* 22209 */
1416 22273, /* 22273 */
1417 22307, /* 22337 */
1418 22397, /* 22401 */
1419 22453, /* 22465 */
1420 22511, /* 22529 */
1421 22573, /* 22593 */
1422 22651, /* 22657 */
1423 22721, /* 22721 */
1424 22783, /* 22785 */
1425 22817, /* 22849 */
1426 22907, /* 22913 */
1427 22973, /* 22977 */
1428 23041, /* 23041 */
1429 23099, /* 23105 */
1430 23167, /* 23169 */
1431 23227, /* 23233 */
1432 23297, /* 23297 */
1433 23357, /* 23361 */
1434 23417, /* 23425 */
1435 23473, /* 23489 */
1436 23549, /* 23553 */
1437 23609, /* 23617 */
1438 23677, /* 23681 */
1439 23743, /* 23745 */
1440 23801, /* 23809 */
1441 23873, /* 23873 */
1442 23929, /* 23937 */
1443 24001, /* 24001 */
1444 24061, /* 24065 */
1445 24121, /* 24129 */
1446 24181, /* 24193 */
1447 24251, /* 24257 */
1448 24317, /* 24321 */
1449 24379, /* 24385 */
1450 24443, /* 24449 */
1451 24509, /* 24513 */
1452 24571, /* 24577 */
1453 24631, /* 24641 */
1454 24697, /* 24705 */
1455 24767, /* 24769 */
1456 24821, /* 24833 */
1457 24889, /* 24897 */
1458 24953, /* 24961 */
1459 25013, /* 25025 */
1460 25087, /* 25089 */
1461 25153, /* 25153 */
1462 25189, /* 25217 */
1463 25261, /* 25281 */
1464 25343, /* 25345 */
1465 25409, /* 25409 */
1466 25471, /* 25473 */
1467 25537, /* 25537 */
1468 25601, /* 25601 */
1469 25657, /* 25665 */
1470 25717, /* 25729 */
1471 25793, /* 25793 */
1472 25849, /* 25857 */
1473 25919, /* 25921 */
1474 25981, /* 25985 */
1475 26041, /* 26049 */
1476 26113, /* 26113 */
1477 26177, /* 26177 */
1478 26237, /* 26241 */
1479 26297, /* 26305 */
1480 26357, /* 26369 */
1481 26431, /* 26433 */
1482 26497, /* 26497 */
1483 26561, /* 26561 */
1484 26597, /* 26625 */
1485 26687, /* 26689 */
1486 26737, /* 26753 */
1487 26813, /* 26817 */
1488 26881, /* 26881 */
1489 26927, /* 26945 */
1490 26993, /* 27009 */
1491 27073, /* 27073 */
1492 27127, /* 27137 */
1493 27197, /* 27201 */
1494 27259, /* 27265 */
1495 27329, /* 27329 */
1496 27367, /* 27393 */
1497 27457, /* 27457 */
1498 27509, /* 27521 */
1499 27583, /* 27585 */
1500 27647, /* 27649 */
1501 27701, /* 27713 */
1502 27773, /* 27777 */
1503 27827, /* 27841 */
1504 27901, /* 27905 */
1505 27967, /* 27969 */
1506 28031, /* 28033 */
1507 28097, /* 28097 */
1508 28151, /* 28161 */
1509 28219, /* 28225 */
1510 28289, /* 28289 */
1511 28351, /* 28353 */
1512 28411, /* 28417 */
1513 28477, /* 28481 */
1514 28541, /* 28545 */
1515 28607, /* 28609 */
1516 28669, /* 28673 */
1517 28729, /* 28737 */
1518 28793, /* 28801 */
1519 28859, /* 28865 */
1520 28927, /* 28929 */
1521 28979, /* 28993 */
1522 29033, /* 29057 */
1523 29101, /* 29121 */
1524 29179, /* 29185 */
1525 29243, /* 29249 */
1526 29311, /* 29313 */
1527 29363, /* 29377 */
1528 29437, /* 29441 */
1529 29501, /* 29505 */
1530 29569, /* 29569 */
1531 29633, /* 29633 */
1532 29683, /* 29697 */
1533 29761, /* 29761 */
1534 29819, /* 29825 */
1535 29881, /* 29889 */
1536 29947, /* 29953 */
1537 30013, /* 30017 */
1538 30071, /* 30081 */
1539 30139, /* 30145 */
1540 30203, /* 30209 */
1541 30271, /* 30273 */
1542 30323, /* 30337 */
1543 30391, /* 30401 */
1544 30449, /* 30465 */
1545 30529, /* 30529 */
1546 30593, /* 30593 */
1547 30649, /* 30657 */
1548 30713, /* 30721 */
1549 30781, /* 30785 */
1550 30841, /* 30849 */
1551 30911, /* 30913 */
1552 30977, /* 30977 */
1553 31039, /* 31041 */
1554 31091, /* 31105 */
1555 31159, /* 31169 */
1556 31231, /* 31233 */
1557 31277, /* 31297 */
1558 31357, /* 31361 */
1559 31397, /* 31425 */
1560 31489, /* 31489 */
1561 31547, /* 31553 */
1562 31607, /* 31617 */
1563 31667, /* 31681 */
1564 31741, /* 31745 */
1565 31799, /* 31809 */
1566 31873, /* 31873 */
1567 31907, /* 31937 */
1568 31991, /* 32001 */
1569 32063, /* 32065 */
1570 32119, /* 32129 */
1571 32191, /* 32193 */
1572 32257, /* 32257 */
1573 32321, /* 32321 */
1574 32381, /* 32385 */
1575 32443, /* 32449 */
1576 32507, /* 32513 */
1577 32573, /* 32577 */
1578 32633, /* 32641 */
1579 32693, /* 32705 */
1580 32749, /* 32769 */
1581 32833, /* 32833 */
1582 32887, /* 32897 */
1583 32957, /* 32961 */
1584 33023, /* 33025 */
1585 33083, /* 33089 */
1586 33151, /* 33153 */
1587 33211, /* 33217 */
1588 33247, /* 33281 */
1589 33343, /* 33345 */
1590 33409, /* 33409 */
1591 33469, /* 33473 */
1592 33533, /* 33537 */
1593 33601, /* 33601 */
1594 33647, /* 33665 */
1595 33721, /* 33729 */
1596 33791, /* 33793 */
1597 33857, /* 33857 */
1598 33911, /* 33921 */
1599 33967, /* 33985 */
1600 34039, /* 34049 */
1601 34061, /* 34113 */
1602 34171, /* 34177 */
1603 34231, /* 34241 */
1604 34303, /* 34305 */
1605 34369, /* 34369 */
1606 34429, /* 34433 */
1607 34487, /* 34497 */
1608 34549, /* 34561 */
1609 34613, /* 34625 */
1610 34687, /* 34689 */
1611 34747, /* 34753 */
1612 34807, /* 34817 */
1613 34877, /* 34881 */
1614 34939, /* 34945 */
1615 34981, /* 35009 */
1616 35069, /* 35073 */
1617 35129, /* 35137 */
1618 35201, /* 35201 */
1619 35257, /* 35265 */
1620 35327, /* 35329 */
1621 35393, /* 35393 */
1622 35449, /* 35457 */
1623 35521, /* 35521 */
1624 35573, /* 35585 */
1625 35617, /* 35649 */
1626 35677, /* 35713 */
1627 35771, /* 35777 */
1628 35839, /* 35841 */
1629 35899, /* 35905 */
1630 35969, /* 35969 */
1631 36017, /* 36033 */
1632 36097, /* 36097 */
1633 36161, /* 36161 */
1634 36217, /* 36225 */
1635 36277, /* 36289 */
1636 36353, /* 36353 */
1637 36389, /* 36417 */
1638 36479, /* 36481 */
1639 36541, /* 36545 */
1640 36607, /* 36609 */
1641 36671, /* 36673 */
1642 36721, /* 36737 */
1643 36793, /* 36801 */
1644 36857, /* 36865 */
1645 36929, /* 36929 */
1646 36979, /* 36993 */
1647 37057, /* 37057 */
1648 37117, /* 37121 */
1649 37181, /* 37185 */
1650 37243, /* 37249 */
1651 37313, /* 37313 */
1652 37369, /* 37377 */
1653 37441, /* 37441 */
1654 37501, /* 37505 */
1655 37567, /* 37569 */
1656 37633, /* 37633 */
1657 37693, /* 37697 */
1658 37747, /* 37761 */
1659 37813, /* 37825 */
1660 37889, /* 37889 */
1661 37951, /* 37953 */
1662 38011, /* 38017 */
1663 38069, /* 38081 */
1664 38119, /* 38145 */
1665 38201, /* 38209 */
1666 38273, /* 38273 */
1667 38333, /* 38337 */
1668 38393, /* 38401 */
1669 38461, /* 38465 */
1670 38501, /* 38529 */
1671 38593, /* 38593 */
1672 38653, /* 38657 */
1673 38713, /* 38721 */
1674 38783, /* 38785 */
1675 38839, /* 38849 */
1676 38903, /* 38913 */
1677 38977, /* 38977 */
1678 39041, /* 39041 */
1679 39103, /* 39105 */
1680 39163, /* 39169 */
1681 39233, /* 39233 */
1682 39293, /* 39297 */
1683 39359, /* 39361 */
1684 39419, /* 39425 */
1685 39461, /* 39489 */
1686 39551, /* 39553 */
1687 39607, /* 39617 */
1688 39679, /* 39681 */
1689 39733, /* 39745 */
1690 39799, /* 39809 */
1691 39869, /* 39873 */
1692 39937, /* 39937 */
1693 39989, /* 40001 */
1694 40063, /* 40065 */
1695 40129, /* 40129 */
1696 40193, /* 40193 */
1697 40253, /* 40257 */
1698 40289, /* 40321 */
1699 40361, /* 40385 */
1700 40433, /* 40449 */
1701 40507, /* 40513 */
1702 40577, /* 40577 */
1703 40639, /* 40641 */
1704 40699, /* 40705 */
1705 40763, /* 40769 */
1706 40829, /* 40833 */
1707 40897, /* 40897 */
1708 40961, /* 40961 */
1709 41023, /* 41025 */
1710 41081, /* 41089 */
1711 41149, /* 41153 */
1712 41213, /* 41217 */
1713 41281, /* 41281 */
1714 41341, /* 41345 */
1715 41399, /* 41409 */
1716 41467, /* 41473 */
1717 41521, /* 41537 */
1718 41597, /* 41601 */
1719 41659, /* 41665 */
1720 41729, /* 41729 */
1721 41777, /* 41793 */
1722 41851, /* 41857 */
1723 41911, /* 41921 */
1724 41983, /* 41985 */
1725 42043, /* 42049 */
1726 42101, /* 42113 */
1727 42169, /* 42177 */
1728 42239, /* 42241 */
1729 42299, /* 42305 */
1730 42359, /* 42369 */
1731 42433, /* 42433 */
1732 42491, /* 42497 */
1733 42557, /* 42561 */
1734 42611, /* 42625 */
1735 42689, /* 42689 */
1736 42751, /* 42753 */
1737 42797, /* 42817 */
1738 42863, /* 42881 */
1739 42943, /* 42945 */
1740 43003, /* 43009 */
1741 43067, /* 43073 */
1742 43133, /* 43137 */
1743 43201, /* 43201 */
1744 43261, /* 43265 */
1745 43321, /* 43329 */
1746 43391, /* 43393 */
1747 43457, /* 43457 */
1748 43517, /* 43521 */
1749 43579, /* 43585 */
1750 43649, /* 43649 */
1751 43711, /* 43713 */
1752 43777, /* 43777 */
1753 43801, /* 43841 */
1754 43891, /* 43905 */
1755 43969, /* 43969 */
1756 44029, /* 44033 */
1757 44089, /* 44097 */
1758 44159, /* 44161 */
1759 44221, /* 44225 */
1760 44281, /* 44289 */
1761 44351, /* 44353 */
1762 44417, /* 44417 */
1763 44453, /* 44481 */
1764 44543, /* 44545 */
1765 44587, /* 44609 */
1766 44657, /* 44673 */
1767 44729, /* 44737 */
1768 44797, /* 44801 */
1769 44851, /* 44865 */
1770 44927, /* 44929 */
1771 44987, /* 44993 */
1772 45053, /* 45057 */
1773 45121, /* 45121 */
1774 45181, /* 45185 */
1775 45247, /* 45249 */
1776 45307, /* 45313 */
1777 45377, /* 45377 */
1778 45439, /* 45441 */
1779 45503, /* 45505 */
1780 45569, /* 45569 */
1781 45631, /* 45633 */
1782 45697, /* 45697 */
1783 45757, /* 45761 */
1784 45823, /* 45825 */
1785 45887, /* 45889 */
1786 45953, /* 45953 */
1787 45989, /* 46017 */
1788 46073, /* 46081 */
1789 46141, /* 46145 */
1790 46199, /* 46209 */
1791 46273, /* 46273 */
1792 46337, /* 46337 */
1793 46399, /* 46401 */
1794 46457, /* 46465 */
1795 46523, /* 46529 */
1796 46591, /* 46593 */
1797 46649, /* 46657 */
1798 46703, /* 46721 */
1799 46771, /* 46785 */
1800 46831, /* 46849 */
1801 46901, /* 46913 */
1802 46957, /* 46977 */
1803 47041, /* 47041 */
1804 47093, /* 47105 */
1805 47161, /* 47169 */
1806 47221, /* 47233 */
1807 47297, /* 47297 */
1808 47353, /* 47361 */
1809 47419, /* 47425 */
1810 47459, /* 47489 */
1811 47543, /* 47553 */
1812 47609, /* 47617 */
1813 47681, /* 47681 */
1814 47743, /* 47745 */
1815 47809, /* 47809 */
1816 47869, /* 47873 */
1817 47933, /* 47937 */
1818 47981, /* 48001 */
1819 48049, /* 48065 */
1820 48121, /* 48129 */
1821 48193, /* 48193 */
1822 48247, /* 48257 */
1823 48313, /* 48321 */
1824 48383, /* 48385 */
1825 48449, /* 48449 */
1826 48497, /* 48513 */
1827 48571, /* 48577 */
1828 48623, /* 48641 */
1829 48679, /* 48705 */
1830 48767, /* 48769 */
1831 48823, /* 48833 */
1832 48889, /* 48897 */
1833 48953, /* 48961 */
1834 49019, /* 49025 */
1835 49081, /* 49089 */
1836 49139, /* 49153 */
1837 49211, /* 49217 */
1838 49279, /* 49281 */
1839 49339, /* 49345 */
1840 49409, /* 49409 */
1841 49463, /* 49473 */
1842 49537, /* 49537 */
1843 49597, /* 49601 */
1844 49663, /* 49665 */
1845 49727, /* 49729 */
1846 49789, /* 49793 */
1847 49853, /* 49857 */
1848 49921, /* 49921 */
1849 49957, /* 49985 */
1850 50047, /* 50049 */
1851 50111, /* 50113 */
1852 50177, /* 50177 */
1853 50231, /* 50241 */
1854 50291, /* 50305 */
1855 50363, /* 50369 */
1856 50423, /* 50433 */
1857 50497, /* 50497 */
1858 50551, /* 50561 */
1859 50599, /* 50625 */
1860 50683, /* 50689 */
1861 50753, /* 50753 */
1862 50789, /* 50817 */
1863 50873, /* 50881 */
1864 50929, /* 50945 */
1865 51001, /* 51009 */
1866 51071, /* 51073 */
1867 51137, /* 51137 */
1868 51199, /* 51201 */
1869 51263, /* 51265 */
1870 51329, /* 51329 */
1871 51383, /* 51393 */
1872 51449, /* 51457 */
1873 51521, /* 51521 */
1874 51581, /* 51585 */
1875 51647, /* 51649 */
1876 51713, /* 51713 */
1877 51769, /* 51777 */
1878 51839, /* 51841 */
1879 51899, /* 51905 */
1880 51949, /* 51969 */
1881 52027, /* 52033 */
1882 52081, /* 52097 */
1883 52153, /* 52161 */
1884 52223, /* 52225 */
1885 52289, /* 52289 */
1886 52321, /* 52353 */
1887 52391, /* 52417 */
1888 52457, /* 52481 */
1889 52543, /* 52545 */
1890 52609, /* 52609 */
1891 52673, /* 52673 */
1892 52733, /* 52737 */
1893 52783, /* 52801 */
1894 52861, /* 52865 */
1895 52919, /* 52929 */
1896 52981, /* 52993 */
1897 53051, /* 53057 */
1898 53117, /* 53121 */
1899 53173, /* 53185 */
1900 53239, /* 53249 */
1901 53309, /* 53313 */
1902 53377, /* 53377 */
1903 53441, /* 53441 */
1904 53503, /* 53505 */
1905 53569, /* 53569 */
1906 53633, /* 53633 */
1907 53693, /* 53697 */
1908 53759, /* 53761 */
1909 53819, /* 53825 */
1910 53887, /* 53889 */
1911 53951, /* 53953 */
1912 54013, /* 54017 */
1913 54059, /* 54081 */
1914 54139, /* 54145 */
1915 54193, /* 54209 */
1916 54269, /* 54273 */
1917 54331, /* 54337 */
1918 54401, /* 54401 */
1919 54449, /* 54465 */
1920 54521, /* 54529 */
1921 54583, /* 54593 */
1922 54647, /* 54657 */
1923 54721, /* 54721 */
1924 54779, /* 54785 */
1925 54833, /* 54849 */
1926 54907, /* 54913 */
1927 54973, /* 54977 */
1928 55021, /* 55041 */
1929 55103, /* 55105 */
1930 55163, /* 55169 */
1931 55229, /* 55233 */
1932 55291, /* 55297 */
1933 55351, /* 55361 */
1934 55411, /* 55425 */
1935 55487, /* 55489 */
1936 55547, /* 55553 */
1937 55609, /* 55617 */
1938 55681, /* 55681 */
1939 55733, /* 55745 */
1940 55807, /* 55809 */
1941 55871, /* 55873 */
1942 55933, /* 55937 */
1943 55997, /* 56001 */
1944 56053, /* 56065 */
1945 56123, /* 56129 */
1946 56179, /* 56193 */
1947 56249, /* 56257 */
1948 56311, /* 56321 */
1949 56383, /* 56385 */
1950 56443, /* 56449 */
1951 56509, /* 56513 */
1952 56569, /* 56577 */
1953 56633, /* 56641 */
1954 56701, /* 56705 */
1955 56767, /* 56769 */
1956 56827, /* 56833 */
1957 56897, /* 56897 */
1958 56957, /* 56961 */
1959 56999, /* 57025 */
1960 57089, /* 57089 */
1961 57149, /* 57153 */
1962 57203, /* 57217 */
1963 57271, /* 57281 */
1964 57331, /* 57345 */
1965 57397, /* 57409 */
1966 57467, /* 57473 */
1967 57529, /* 57537 */
1968 57601, /* 57601 */
1969 57653, /* 57665 */
1970 57727, /* 57729 */
1971 57793, /* 57793 */
1972 57853, /* 57857 */
1973 57917, /* 57921 */
1974 57977, /* 57985 */
1975 58049, /* 58049 */
1976 58111, /* 58113 */
1977 58171, /* 58177 */
1978 58237, /* 58241 */
1979 58271, /* 58305 */
1980 58369, /* 58369 */
1981 58427, /* 58433 */
1982 58481, /* 58497 */
1983 58549, /* 58561 */
1984 58613, /* 58625 */
1985 58687, /* 58689 */
1986 58741, /* 58753 */
1987 58789, /* 58817 */
1988 58831, /* 58881 */
1989 58943, /* 58945 */
1990 59009, /* 59009 */
1991 59069, /* 59073 */
1992 59123, /* 59137 */
1993 59197, /* 59201 */
1994 59263, /* 59265 */
1995 59281, /* 59329 */
1996 59393, /* 59393 */
1997 59453, /* 59457 */
1998 59513, /* 59521 */
1999 59581, /* 59585 */
2000 59629, /* 59649 */
2001 59707, /* 59713 */
2002 59771, /* 59777 */
2003 59833, /* 59841 */
2004 59887, /* 59905 */
2005 59957, /* 59969 */
2006 60029, /* 60033 */
2007 60091, /* 60097 */
2008 60161, /* 60161 */
2009 60223, /* 60225 */
2010 60289, /* 60289 */
2011 60353, /* 60353 */
2012 60413, /* 60417 */
2013 60457, /* 60481 */
2014 60539, /* 60545 */
2015 60607, /* 60609 */
2016 60661, /* 60673 */
2017 60737, /* 60737 */
2018 60793, /* 60801 */
2019 60859, /* 60865 */
2020 60923, /* 60929 */
2021 60961, /* 60993 */
2022 61057, /* 61057 */
2023 61121, /* 61121 */
2024 61169, /* 61185 */
2025 61231, /* 61249 */
2026 61297, /* 61313 */
2027 61363, /* 61377 */
2028 61441, /* 61441 */
2029 61493, /* 61505 */
2030 61561, /* 61569 */
2031 61631, /* 61633 */
2032 61687, /* 61697 */
2033 61757, /* 61761 */
2034 61819, /* 61825 */
2035 61879, /* 61889 */
2036 61949, /* 61953 */
2037 62017, /* 62017 */
2038 62081, /* 62081 */
2039 62143, /* 62145 */
2040 62207, /* 62209 */
2041 62273, /* 62273 */
2042 62327, /* 62337 */
2043 62401, /* 62401 */
2044 62459, /* 62465 */
2045 62507, /* 62529 */
2046 62591, /* 62593 */
2047 62653, /* 62657 */
2048 62701, /* 62721 */
2049 62773, /* 62785 */
2050 62827, /* 62849 */
2051 62903, /* 62913 */
2052 62971, /* 62977 */
2053 63031, /* 63041 */
2054 63103, /* 63105 */
2055 63149, /* 63169 */
2056 63211, /* 63233 */
2057 63281, /* 63297 */
2058 63361, /* 63361 */
2059 63421, /* 63425 */
2060 63487, /* 63489 */
2061 63541, /* 63553 */
2062 63617, /* 63617 */
2063 63671, /* 63681 */
2064 63743, /* 63745 */
2065 63809, /* 63809 */
2066 63863, /* 63873 */
2067 63929, /* 63937 */
2068 63997, /* 64001 */
2069 64063, /* 64065 */
2070 64123, /* 64129 */
2071 64189, /* 64193 */
2072 64237, /* 64257 */
2073 64319, /* 64321 */
2074 64381, /* 64385 */
2075 64439, /* 64449 */
2076 64513, /* 64513 */
2077 64577, /* 64577 */
2078 64633, /* 64641 */
2079 64693, /* 64705 */
2080 64763, /* 64769 */
2081 64817, /* 64833 */
2082 64891, /* 64897 */
2083 64951, /* 64961 */
2084 65011, /* 65025 */
2085 65089, /* 65089 */
2086 65147, /* 65153 */
2087 65213, /* 65217 */
2088 65269, /* 65281 */
2089 65327, /* 65345 */
2090 65407, /* 65409 */
2091 65449, /* 65473 */
2092 };
2093 /* 0-1M, increments=1024 */
2094 static
2095 unsigned prime_table2[1024]={
2096 1021, /* 1024 */
2097 2039, /* 2048 */
2098 3067, /* 3072 */
2099 4093, /* 4096 */
2100 5119, /* 5120 */
2101 6143, /* 6144 */
2102 7159, /* 7168 */
2103 8191, /* 8192 */
2104 9209, /* 9216 */
2105 10223, /* 10240 */
2106 11261, /* 11264 */
2107 12281, /* 12288 */
2108 13309, /* 13312 */
2109 14327, /* 14336 */
2110 15359, /* 15360 */
2111 16381, /* 16384 */
2112 17401, /* 17408 */
2113 18427, /* 18432 */
2114 19447, /* 19456 */
2115 20479, /* 20480 */
2116 21503, /* 21504 */
2117 22511, /* 22528 */
2118 23549, /* 23552 */
2119 24571, /* 24576 */
2120 25589, /* 25600 */
2121 26597, /* 26624 */
2122 27647, /* 27648 */
2123 28669, /* 28672 */
2124 29683, /* 29696 */
2125 30713, /* 30720 */
2126 31741, /* 31744 */
2127 32749, /* 32768 */
2128 33791, /* 33792 */
2129 34807, /* 34816 */
2130 35839, /* 35840 */
2131 36857, /* 36864 */
2132 37879, /* 37888 */
2133 38903, /* 38912 */
2134 39929, /* 39936 */
2135 40949, /* 40960 */
2136 41983, /* 41984 */
2137 43003, /* 43008 */
2138 44029, /* 44032 */
2139 45053, /* 45056 */
2140 46073, /* 46080 */
2141 47093, /* 47104 */
2142 48121, /* 48128 */
2143 49139, /* 49152 */
2144 50159, /* 50176 */
2145 51199, /* 51200 */
2146 52223, /* 52224 */
2147 53239, /* 53248 */
2148 54269, /* 54272 */
2149 55291, /* 55296 */
2150 56311, /* 56320 */
2151 57331, /* 57344 */
2152 58367, /* 58368 */
2153 59387, /* 59392 */
2154 60413, /* 60416 */
2155 61417, /* 61440 */
2156 62459, /* 62464 */
2157 63487, /* 63488 */
2158 64499, /* 64512 */
2159 65521, /* 65536 */
2160 66553, /* 66560 */
2161 67579, /* 67584 */
2162 68597, /* 68608 */
2163 69623, /* 69632 */
2164 70639, /* 70656 */
2165 71671, /* 71680 */
2166 72701, /* 72704 */
2167 73727, /* 73728 */
2168 74747, /* 74752 */
2169 75773, /* 75776 */
2170 76781, /* 76800 */
2171 77813, /* 77824 */
2172 78839, /* 78848 */
2173 79867, /* 79872 */
2174 80863, /* 80896 */
2175 81919, /* 81920 */
2176 82939, /* 82944 */
2177 83939, /* 83968 */
2178 84991, /* 84992 */
2179 86011, /* 86016 */
2180 87037, /* 87040 */
2181 88037, /* 88064 */
2182 89087, /* 89088 */
2183 90107, /* 90112 */
2184 91129, /* 91136 */
2185 92153, /* 92160 */
2186 93179, /* 93184 */
2187 94207, /* 94208 */
2188 95231, /* 95232 */
2189 96233, /* 96256 */
2190 97259, /* 97280 */
2191 98299, /* 98304 */
2192 99317, /* 99328 */
2193 100343, /* 100352 */
2194 101363, /* 101376 */
2195 102397, /* 102400 */
2196 103423, /* 103424 */
2197 104417, /* 104448 */
2198 105467, /* 105472 */
2199 106487, /* 106496 */
2200 107509, /* 107520 */
2201 108541, /* 108544 */
2202 109567, /* 109568 */
2203 110587, /* 110592 */
2204 111611, /* 111616 */
2205 112621, /* 112640 */
2206 113657, /* 113664 */
2207 114679, /* 114688 */
2208 115693, /* 115712 */
2209 116731, /* 116736 */
2210 117757, /* 117760 */
2211 118757, /* 118784 */
2212 119797, /* 119808 */
2213 120829, /* 120832 */
2214 121853, /* 121856 */
2215 122869, /* 122880 */
2216 123887, /* 123904 */
2217 124919, /* 124928 */
2218 125941, /* 125952 */
2219 126967, /* 126976 */
2220 127997, /* 128000 */
2221 129023, /* 129024 */
2222 130043, /* 130048 */
2223 131071, /* 131072 */
2224 132071, /* 132096 */
2225 133117, /* 133120 */
2226 134129, /* 134144 */
2227 135151, /* 135168 */
2228 136189, /* 136192 */
2229 137209, /* 137216 */
2230 138239, /* 138240 */
2231 139241, /* 139264 */
2232 140281, /* 140288 */
2233 141311, /* 141312 */
2234 142327, /* 142336 */
2235 143357, /* 143360 */
2236 144383, /* 144384 */
2237 145399, /* 145408 */
2238 146423, /* 146432 */
2239 147451, /* 147456 */
2240 148471, /* 148480 */
2241 149503, /* 149504 */
2242 150523, /* 150528 */
2243 151549, /* 151552 */
2244 152567, /* 152576 */
2245 153589, /* 153600 */
2246 154621, /* 154624 */
2247 155627, /* 155648 */
2248 156671, /* 156672 */
2249 157679, /* 157696 */
2250 158699, /* 158720 */
2251 159739, /* 159744 */
2252 160757, /* 160768 */
2253 161783, /* 161792 */
2254 162791, /* 162816 */
2255 163819, /* 163840 */
2256 164839, /* 164864 */
2257 165887, /* 165888 */
2258 166909, /* 166912 */
2259 167917, /* 167936 */
2260 168943, /* 168960 */
2261 169957, /* 169984 */
2262 171007, /* 171008 */
2263 172031, /* 172032 */
2264 173053, /* 173056 */
2265 174079, /* 174080 */
2266 175103, /* 175104 */
2267 176123, /* 176128 */
2268 177131, /* 177152 */
2269 178169, /* 178176 */
2270 179173, /* 179200 */
2271 180221, /* 180224 */
2272 181243, /* 181248 */
2273 182261, /* 182272 */
2274 183289, /* 183296 */
2275 184309, /* 184320 */
2276 185327, /* 185344 */
2277 186343, /* 186368 */
2278 187387, /* 187392 */
2279 188407, /* 188416 */
2280 189439, /* 189440 */
2281 190409, /* 190464 */
2282 191473, /* 191488 */
2283 192499, /* 192512 */
2284 193513, /* 193536 */
2285 194543, /* 194560 */
2286 195581, /* 195584 */
2287 196597, /* 196608 */
2288 197621, /* 197632 */
2289 198647, /* 198656 */
2290 199679, /* 199680 */
2291 200699, /* 200704 */
2292 201709, /* 201728 */
2293 202751, /* 202752 */
2294 203773, /* 203776 */
2295 204797, /* 204800 */
2296 205823, /* 205824 */
2297 206827, /* 206848 */
2298 207869, /* 207872 */
2299 208891, /* 208896 */
2300 209917, /* 209920 */
2301 210943, /* 210944 */
2302 211949, /* 211968 */
2303 212987, /* 212992 */
2304 214009, /* 214016 */
2305 214993, /* 215040 */
2306 216061, /* 216064 */
2307 217081, /* 217088 */
2308 218111, /* 218112 */
2309 219133, /* 219136 */
2310 220151, /* 220160 */
2311 221173, /* 221184 */
2312 222199, /* 222208 */
2313 223229, /* 223232 */
2314 224251, /* 224256 */
2315 225263, /* 225280 */
2316 226283, /* 226304 */
2317 227303, /* 227328 */
2318 228341, /* 228352 */
2319 229373, /* 229376 */
2320 230393, /* 230400 */
2321 231419, /* 231424 */
2322 232439, /* 232448 */
2323 233437, /* 233472 */
2324 234473, /* 234496 */
2325 235519, /* 235520 */
2326 236527, /* 236544 */
2327 237563, /* 237568 */
2328 238591, /* 238592 */
2329 239611, /* 239616 */
2330 240631, /* 240640 */
2331 241663, /* 241664 */
2332 242681, /* 242688 */
2333 243709, /* 243712 */
2334 244733, /* 244736 */
2335 245759, /* 245760 */
2336 246781, /* 246784 */
2337 247799, /* 247808 */
2338 248827, /* 248832 */
2339 249853, /* 249856 */
2340 250871, /* 250880 */
2341 251903, /* 251904 */
2342 252919, /* 252928 */
2343 253951, /* 253952 */
2344 254971, /* 254976 */
2345 255989, /* 256000 */
2346 257017, /* 257024 */
2347 258031, /* 258048 */
2348 259033, /* 259072 */
2349 260089, /* 260096 */
2350 261101, /* 261120 */
2351 262139, /* 262144 */
2352 263167, /* 263168 */
2353 264179, /* 264192 */
2354 265207, /* 265216 */
2355 266239, /* 266240 */
2356 267259, /* 267264 */
2357 268283, /* 268288 */
2358 269281, /* 269312 */
2359 270329, /* 270336 */
2360 271357, /* 271360 */
2361 272383, /* 272384 */
2362 273367, /* 273408 */
2363 274423, /* 274432 */
2364 275453, /* 275456 */
2365 276467, /* 276480 */
2366 277499, /* 277504 */
2367 278503, /* 278528 */
2368 279551, /* 279552 */
2369 280561, /* 280576 */
2370 281581, /* 281600 */
2371 282617, /* 282624 */
2372 283639, /* 283648 */
2373 284659, /* 284672 */
2374 285673, /* 285696 */
2375 286711, /* 286720 */
2376 287731, /* 287744 */
2377 288767, /* 288768 */
2378 289789, /* 289792 */
2379 290803, /* 290816 */
2380 291833, /* 291840 */
2381 292849, /* 292864 */
2382 293863, /* 293888 */
2383 294911, /* 294912 */
2384 295909, /* 295936 */
2385 296941, /* 296960 */
2386 297971, /* 297984 */
2387 298999, /* 299008 */
2388 300023, /* 300032 */
2389 301051, /* 301056 */
2390 302053, /* 302080 */
2391 303097, /* 303104 */
2392 304127, /* 304128 */
2393 305147, /* 305152 */
2394 306169, /* 306176 */
2395 307189, /* 307200 */
2396 308219, /* 308224 */
2397 309241, /* 309248 */
2398 310243, /* 310272 */
2399 311293, /* 311296 */
2400 312313, /* 312320 */
2401 313343, /* 313344 */
2402 314359, /* 314368 */
2403 315389, /* 315392 */
2404 316403, /* 316416 */
2405 317437, /* 317440 */
2406 318457, /* 318464 */
2407 319483, /* 319488 */
2408 320483, /* 320512 */
2409 321509, /* 321536 */
2410 322559, /* 322560 */
2411 323581, /* 323584 */
2412 324593, /* 324608 */
2413 325631, /* 325632 */
2414 326633, /* 326656 */
2415 327673, /* 327680 */
2416 328687, /* 328704 */
2417 329723, /* 329728 */
2418 330749, /* 330752 */
2419 331769, /* 331776 */
2420 332791, /* 332800 */
2421 333821, /* 333824 */
2422 334843, /* 334848 */
2423 335857, /* 335872 */
2424 336887, /* 336896 */
2425 337919, /* 337920 */
2426 338927, /* 338944 */
2427 339959, /* 339968 */
2428 340979, /* 340992 */
2429 341993, /* 342016 */
2430 343037, /* 343040 */
2431 344053, /* 344064 */
2432 345067, /* 345088 */
2433 346111, /* 346112 */
2434 347131, /* 347136 */
2435 348149, /* 348160 */
2436 349183, /* 349184 */
2437 350191, /* 350208 */
2438 351229, /* 351232 */
2439 352249, /* 352256 */
2440 353263, /* 353280 */
2441 354301, /* 354304 */
2442 355321, /* 355328 */
2443 356351, /* 356352 */
2444 357359, /* 357376 */
2445 358373, /* 358400 */
2446 359419, /* 359424 */
2447 360439, /* 360448 */
2448 361469, /* 361472 */
2449 362473, /* 362496 */
2450 363497, /* 363520 */
2451 364543, /* 364544 */
2452 365567, /* 365568 */
2453 366547, /* 366592 */
2454 367613, /* 367616 */
2455 368633, /* 368640 */
2456 369661, /* 369664 */
2457 370687, /* 370688 */
2458 371699, /* 371712 */
2459 372733, /* 372736 */
2460 373757, /* 373760 */
2461 374783, /* 374784 */
2462 375799, /* 375808 */
2463 376823, /* 376832 */
2464 377851, /* 377856 */
2465 378869, /* 378880 */
2466 379903, /* 379904 */
2467 380917, /* 380928 */
2468 381949, /* 381952 */
2469 382961, /* 382976 */
2470 383987, /* 384000 */
2471 385013, /* 385024 */
2472 386047, /* 386048 */
2473 387071, /* 387072 */
2474 388081, /* 388096 */
2475 389117, /* 389120 */
2476 390119, /* 390144 */
2477 391163, /* 391168 */
2478 392177, /* 392192 */
2479 393209, /* 393216 */
2480 394223, /* 394240 */
2481 395261, /* 395264 */
2482 396269, /* 396288 */
2483 397303, /* 397312 */
2484 398323, /* 398336 */
2485 399353, /* 399360 */
2486 400381, /* 400384 */
2487 401407, /* 401408 */
2488 402419, /* 402432 */
2489 403439, /* 403456 */
2490 404461, /* 404480 */
2491 405499, /* 405504 */
2492 406517, /* 406528 */
2493 407527, /* 407552 */
2494 408563, /* 408576 */
2495 409597, /* 409600 */
2496 410623, /* 410624 */
2497 411641, /* 411648 */
2498 412667, /* 412672 */
2499 413689, /* 413696 */
2500 414709, /* 414720 */
2501 415729, /* 415744 */
2502 416761, /* 416768 */
2503 417773, /* 417792 */
2504 418813, /* 418816 */
2505 419831, /* 419840 */
2506 420859, /* 420864 */
2507 421847, /* 421888 */
2508 422911, /* 422912 */
2509 423931, /* 423936 */
2510 424939, /* 424960 */
2511 425977, /* 425984 */
2512 427001, /* 427008 */
2513 428027, /* 428032 */
2514 429043, /* 429056 */
2515 430061, /* 430080 */
2516 431099, /* 431104 */
2517 432121, /* 432128 */
2518 433151, /* 433152 */
2519 434167, /* 434176 */
2520 435191, /* 435200 */
2521 436217, /* 436224 */
2522 437243, /* 437248 */
2523 438271, /* 438272 */
2524 439289, /* 439296 */
2525 440311, /* 440320 */
2526 441319, /* 441344 */
2527 442367, /* 442368 */
2528 443389, /* 443392 */
2529 444403, /* 444416 */
2530 445433, /* 445440 */
2531 446461, /* 446464 */
2532 447481, /* 447488 */
2533 448451, /* 448512 */
2534 449473, /* 449536 */
2535 450557, /* 450560 */
2536 451579, /* 451584 */
2537 452597, /* 452608 */
2538 453631, /* 453632 */
2539 454637, /* 454656 */
2540 455659, /* 455680 */
2541 456697, /* 456704 */
2542 457711, /* 457728 */
2543 458747, /* 458752 */
2544 459763, /* 459776 */
2545 460793, /* 460800 */
2546 461819, /* 461824 */
2547 462841, /* 462848 */
2548 463867, /* 463872 */
2549 464879, /* 464896 */
2550 465917, /* 465920 */
2551 466919, /* 466944 */
2552 467963, /* 467968 */
2553 468983, /* 468992 */
2554 469993, /* 470016 */
2555 471007, /* 471040 */
2556 472063, /* 472064 */
2557 473027, /* 473088 */
2558 474101, /* 474112 */
2559 475109, /* 475136 */
2560 476143, /* 476160 */
2561 477163, /* 477184 */
2562 478207, /* 478208 */
2563 479231, /* 479232 */
2564 480209, /* 480256 */
2565 481249, /* 481280 */
2566 482281, /* 482304 */
2567 483323, /* 483328 */
2568 484339, /* 484352 */
2569 485371, /* 485376 */
2570 486397, /* 486400 */
2571 487423, /* 487424 */
2572 488441, /* 488448 */
2573 489457, /* 489472 */
2574 490493, /* 490496 */
2575 491503, /* 491520 */
2576 492523, /* 492544 */
2577 493567, /* 493568 */
2578 494591, /* 494592 */
2579 495613, /* 495616 */
2580 496631, /* 496640 */
2581 497663, /* 497664 */
2582 498679, /* 498688 */
2583 499711, /* 499712 */
2584 500729, /* 500736 */
2585 501731, /* 501760 */
2586 502781, /* 502784 */
2587 503803, /* 503808 */
2588 504821, /* 504832 */
2589 505823, /* 505856 */
2590 506873, /* 506880 */
2591 507901, /* 507904 */
2592 508919, /* 508928 */
2593 509947, /* 509952 */
2594 510943, /* 510976 */
2595 511997, /* 512000 */
2596 513017, /* 513024 */
2597 514021, /* 514048 */
2598 515041, /* 515072 */
2599 516091, /* 516096 */
2600 517091, /* 517120 */
2601 518137, /* 518144 */
2602 519161, /* 519168 */
2603 520151, /* 520192 */
2604 521201, /* 521216 */
2605 522239, /* 522240 */
2606 523261, /* 523264 */
2607 524287, /* 524288 */
2608 525299, /* 525312 */
2609 526307, /* 526336 */
2610 527353, /* 527360 */
2611 528383, /* 528384 */
2612 529393, /* 529408 */
2613 530429, /* 530432 */
2614 531383, /* 531456 */
2615 532453, /* 532480 */
2616 533459, /* 533504 */
2617 534511, /* 534528 */
2618 535547, /* 535552 */
2619 536563, /* 536576 */
2620 537599, /* 537600 */
2621 538621, /* 538624 */
2622 539641, /* 539648 */
2623 540629, /* 540672 */
2624 541693, /* 541696 */
2625 542719, /* 542720 */
2626 543713, /* 543744 */
2627 544759, /* 544768 */
2628 545791, /* 545792 */
2629 546781, /* 546816 */
2630 547831, /* 547840 */
2631 548861, /* 548864 */
2632 549883, /* 549888 */
2633 550909, /* 550912 */
2634 551933, /* 551936 */
2635 552917, /* 552960 */
2636 553981, /* 553984 */
2637 554977, /* 555008 */
2638 556027, /* 556032 */
2639 557041, /* 557056 */
2640 558067, /* 558080 */
2641 559099, /* 559104 */
2642 560123, /* 560128 */
2643 561109, /* 561152 */
2644 562169, /* 562176 */
2645 563197, /* 563200 */
2646 564197, /* 564224 */
2647 565247, /* 565248 */
2648 566233, /* 566272 */
2649 567277, /* 567296 */
2650 568303, /* 568320 */
2651 569323, /* 569344 */
2652 570359, /* 570368 */
2653 571381, /* 571392 */
2654 572399, /* 572416 */
2655 573437, /* 573440 */
2656 574439, /* 574464 */
2657 575479, /* 575488 */
2658 576509, /* 576512 */
2659 577531, /* 577536 */
2660 578537, /* 578560 */
2661 579583, /* 579584 */
2662 580607, /* 580608 */
2663 581617, /* 581632 */
2664 582649, /* 582656 */
2665 583673, /* 583680 */
2666 584699, /* 584704 */
2667 585727, /* 585728 */
2668 586741, /* 586752 */
2669 587773, /* 587776 */
2670 588779, /* 588800 */
2671 589811, /* 589824 */
2672 590839, /* 590848 */
2673 591863, /* 591872 */
2674 592877, /* 592896 */
2675 593903, /* 593920 */
2676 594931, /* 594944 */
2677 595967, /* 595968 */
2678 596987, /* 596992 */
2679 598007, /* 598016 */
2680 599023, /* 599040 */
2681 600053, /* 600064 */
2682 601079, /* 601088 */
2683 602111, /* 602112 */
2684 603133, /* 603136 */
2685 604073, /* 604160 */
2686 605177, /* 605184 */
2687 606181, /* 606208 */
2688 607219, /* 607232 */
2689 608213, /* 608256 */
2690 609277, /* 609280 */
2691 610301, /* 610304 */
2692 611323, /* 611328 */
2693 612349, /* 612352 */
2694 613367, /* 613376 */
2695 614387, /* 614400 */
2696 615413, /* 615424 */
2697 616439, /* 616448 */
2698 617471, /* 617472 */
2699 618463, /* 618496 */
2700 619511, /* 619520 */
2701 620531, /* 620544 */
2702 621541, /* 621568 */
2703 622577, /* 622592 */
2704 623591, /* 623616 */
2705 624607, /* 624640 */
2706 625663, /* 625664 */
2707 626687, /* 626688 */
2708 627709, /* 627712 */
2709 628721, /* 628736 */
2710 629747, /* 629760 */
2711 630737, /* 630784 */
2712 631789, /* 631808 */
2713 632813, /* 632832 */
2714 633833, /* 633856 */
2715 634871, /* 634880 */
2716 635893, /* 635904 */
2717 636919, /* 636928 */
2718 637939, /* 637952 */
2719 638971, /* 638976 */
2720 639997, /* 640000 */
2721 640993, /* 641024 */
2722 642013, /* 642048 */
2723 643061, /* 643072 */
2724 644089, /* 644096 */
2725 645097, /* 645120 */
2726 646103, /* 646144 */
2727 647161, /* 647168 */
2728 648191, /* 648192 */
2729 649183, /* 649216 */
2730 650227, /* 650240 */
2731 651257, /* 651264 */
2732 652283, /* 652288 */
2733 653311, /* 653312 */
2734 654323, /* 654336 */
2735 655357, /* 655360 */
2736 656377, /* 656384 */
2737 657403, /* 657408 */
2738 658417, /* 658432 */
2739 659453, /* 659456 */
2740 660449, /* 660480 */
2741 661483, /* 661504 */
2742 662527, /* 662528 */
2743 663547, /* 663552 */
2744 664571, /* 664576 */
2745 665591, /* 665600 */
2746 666607, /* 666624 */
2747 667643, /* 667648 */
2748 668671, /* 668672 */
2749 669689, /* 669696 */
2750 670711, /* 670720 */
2751 671743, /* 671744 */
2752 672767, /* 672768 */
2753 673787, /* 673792 */
2754 674813, /* 674816 */
2755 675839, /* 675840 */
2756 676861, /* 676864 */
2757 677857, /* 677888 */
2758 678907, /* 678912 */
2759 679933, /* 679936 */
2760 680959, /* 680960 */
2761 681983, /* 681984 */
2762 683003, /* 683008 */
2763 684017, /* 684032 */
2764 685051, /* 685056 */
2765 686057, /* 686080 */
2766 687101, /* 687104 */
2767 688111, /* 688128 */
2768 689141, /* 689152 */
2769 690163, /* 690176 */
2770 691199, /* 691200 */
2771 692221, /* 692224 */
2772 693223, /* 693248 */
2773 694271, /* 694272 */
2774 695293, /* 695296 */
2775 696317, /* 696320 */
2776 697327, /* 697344 */
2777 698359, /* 698368 */
2778 699383, /* 699392 */
2779 700393, /* 700416 */
2780 701419, /* 701440 */
2781 702451, /* 702464 */
2782 703471, /* 703488 */
2783 704507, /* 704512 */
2784 705533, /* 705536 */
2785 706547, /* 706560 */
2786 707573, /* 707584 */
2787 708601, /* 708608 */
2788 709609, /* 709632 */
2789 710641, /* 710656 */
2790 711679, /* 711680 */
2791 712697, /* 712704 */
2792 713681, /* 713728 */
2793 714751, /* 714752 */
2794 715753, /* 715776 */
2795 716789, /* 716800 */
2796 717817, /* 717824 */
2797 718847, /* 718848 */
2798 719839, /* 719872 */
2799 720887, /* 720896 */
2800 721909, /* 721920 */
2801 722933, /* 722944 */
2802 723967, /* 723968 */
2803 724991, /* 724992 */
2804 726013, /* 726016 */
2805 727021, /* 727040 */
2806 728047, /* 728064 */
2807 729073, /* 729088 */
2808 730111, /* 730112 */
2809 731117, /* 731136 */
2810 732157, /* 732160 */
2811 733177, /* 733184 */
2812 734207, /* 734208 */
2813 735211, /* 735232 */
2814 736249, /* 736256 */
2815 737279, /* 737280 */
2816 738301, /* 738304 */
2817 739327, /* 739328 */
2818 740351, /* 740352 */
2819 741373, /* 741376 */
2820 742393, /* 742400 */
2821 743423, /* 743424 */
2822 744431, /* 744448 */
2823 745471, /* 745472 */
2824 746483, /* 746496 */
2825 747499, /* 747520 */
2826 748541, /* 748544 */
2827 749557, /* 749568 */
2828 750571, /* 750592 */
2829 751613, /* 751616 */
2830 752639, /* 752640 */
2831 753659, /* 753664 */
2832 754651, /* 754688 */
2833 755707, /* 755712 */
2834 756727, /* 756736 */
2835 757753, /* 757760 */
2836 758783, /* 758784 */
2837 759799, /* 759808 */
2838 760813, /* 760832 */
2839 761833, /* 761856 */
2840 762877, /* 762880 */
2841 763901, /* 763904 */
2842 764903, /* 764928 */
2843 765949, /* 765952 */
2844 766967, /* 766976 */
2845 767957, /* 768000 */
2846 769019, /* 769024 */
2847 770047, /* 770048 */
2848 771049, /* 771072 */
2849 772091, /* 772096 */
2850 773117, /* 773120 */
2851 774143, /* 774144 */
2852 775163, /* 775168 */
2853 776183, /* 776192 */
2854 777209, /* 777216 */
2855 778237, /* 778240 */
2856 779249, /* 779264 */
2857 780287, /* 780288 */
2858 781309, /* 781312 */
2859 782329, /* 782336 */
2860 783359, /* 783360 */
2861 784379, /* 784384 */
2862 785377, /* 785408 */
2863 786431, /* 786432 */
2864 787447, /* 787456 */
2865 788479, /* 788480 */
2866 789493, /* 789504 */
2867 790523, /* 790528 */
2868 791543, /* 791552 */
2869 792563, /* 792576 */
2870 793591, /* 793600 */
2871 794593, /* 794624 */
2872 795647, /* 795648 */
2873 796657, /* 796672 */
2874 797689, /* 797696 */
2875 798713, /* 798720 */
2876 799741, /* 799744 */
2877 800759, /* 800768 */
2878 801791, /* 801792 */
2879 802811, /* 802816 */
2880 803819, /* 803840 */
2881 804857, /* 804864 */
2882 805877, /* 805888 */
2883 806903, /* 806912 */
2884 807931, /* 807936 */
2885 808957, /* 808960 */
2886 809983, /* 809984 */
2887 810989, /* 811008 */
2888 812011, /* 812032 */
2889 813049, /* 813056 */
2890 814069, /* 814080 */
2891 815063, /* 815104 */
2892 816121, /* 816128 */
2893 817151, /* 817152 */
2894 818173, /* 818176 */
2895 819187, /* 819200 */
2896 820223, /* 820224 */
2897 821209, /* 821248 */
2898 822259, /* 822272 */
2899 823283, /* 823296 */
2900 824287, /* 824320 */
2901 825343, /* 825344 */
2902 826363, /* 826368 */
2903 827389, /* 827392 */
2904 828409, /* 828416 */
2905 829399, /* 829440 */
2906 830449, /* 830464 */
2907 831461, /* 831488 */
2908 832499, /* 832512 */
2909 833509, /* 833536 */
2910 834527, /* 834560 */
2911 835559, /* 835584 */
2912 836573, /* 836608 */
2913 837631, /* 837632 */
2914 838633, /* 838656 */
2915 839669, /* 839680 */
2916 840703, /* 840704 */
2917 841727, /* 841728 */
2918 842747, /* 842752 */
2919 843763, /* 843776 */
2920 844777, /* 844800 */
2921 845809, /* 845824 */
2922 846841, /* 846848 */
2923 847871, /* 847872 */
2924 848893, /* 848896 */
2925 849917, /* 849920 */
2926 850943, /* 850944 */
2927 851957, /* 851968 */
2928 852989, /* 852992 */
2929 853999, /* 854016 */
2930 855031, /* 855040 */
2931 856061, /* 856064 */
2932 857083, /* 857088 */
2933 858103, /* 858112 */
2934 859121, /* 859136 */
2935 860143, /* 860160 */
2936 861167, /* 861184 */
2937 862207, /* 862208 */
2938 863231, /* 863232 */
2939 864251, /* 864256 */
2940 865261, /* 865280 */
2941 866293, /* 866304 */
2942 867319, /* 867328 */
2943 868349, /* 868352 */
2944 869371, /* 869376 */
2945 870391, /* 870400 */
2946 871393, /* 871424 */
2947 872441, /* 872448 */
2948 873469, /* 873472 */
2949 874487, /* 874496 */
2950 875519, /* 875520 */
2951 876529, /* 876544 */
2952 877567, /* 877568 */
2953 878573, /* 878592 */
2954 879607, /* 879616 */
2955 880603, /* 880640 */
2956 881663, /* 881664 */
2957 882659, /* 882688 */
2958 883703, /* 883712 */
2959 884717, /* 884736 */
2960 885737, /* 885760 */
2961 886777, /* 886784 */
2962 887759, /* 887808 */
2963 888827, /* 888832 */
2964 889829, /* 889856 */
2965 890867, /* 890880 */
2966 891899, /* 891904 */
2967 892919, /* 892928 */
2968 893939, /* 893952 */
2969 894973, /* 894976 */
2970 895987, /* 896000 */
2971 897019, /* 897024 */
2972 898033, /* 898048 */
2973 899069, /* 899072 */
2974 900091, /* 900096 */
2975 901111, /* 901120 */
2976 902141, /* 902144 */
2977 903163, /* 903168 */
2978 904181, /* 904192 */
2979 905213, /* 905216 */
2980 906233, /* 906240 */
2981 907259, /* 907264 */
2982 908287, /* 908288 */
2983 909301, /* 909312 */
2984 910307, /* 910336 */
2985 911359, /* 911360 */
2986 912367, /* 912384 */
2987 913397, /* 913408 */
2988 914429, /* 914432 */
2989 915451, /* 915456 */
2990 916477, /* 916480 */
2991 917503, /* 917504 */
2992 918497, /* 918528 */
2993 919531, /* 919552 */
2994 920561, /* 920576 */
2995 921589, /* 921600 */
2996 922619, /* 922624 */
2997 923641, /* 923648 */
2998 924661, /* 924672 */
2999 925679, /* 925696 */
3000 926707, /* 926720 */
3001 927743, /* 927744 */
3002 928703, /* 928768 */
3003 929791, /* 929792 */
3004 930779, /* 930816 */
3005 931837, /* 931840 */
3006 932863, /* 932864 */
3007 933883, /* 933888 */
3008 934909, /* 934912 */
3009 935903, /* 935936 */
3010 936953, /* 936960 */
3011 937969, /* 937984 */
3012 939007, /* 939008 */
3013 940031, /* 940032 */
3014 941041, /* 941056 */
3015 942079, /* 942080 */
3016 943097, /* 943104 */
3017 944123, /* 944128 */
3018 945151, /* 945152 */
3019 946163, /* 946176 */
3020 947197, /* 947200 */
3021 948187, /* 948224 */
3022 949243, /* 949248 */
3023 950269, /* 950272 */
3024 951283, /* 951296 */
3025 952313, /* 952320 */
3026 953341, /* 953344 */
3027 954367, /* 954368 */
3028 955391, /* 955392 */
3029 956401, /* 956416 */
3030 957433, /* 957440 */
3031 958459, /* 958464 */
3032 959479, /* 959488 */
3033 960499, /* 960512 */
3034 961531, /* 961536 */
3035 962543, /* 962560 */
3036 963581, /* 963584 */
3037 964589, /* 964608 */
3038 965623, /* 965632 */
3039 966653, /* 966656 */
3040 967667, /* 967680 */
3041 968699, /* 968704 */
3042 969721, /* 969728 */
3043 970747, /* 970752 */
3044 971767, /* 971776 */
3045 972799, /* 972800 */
3046 973823, /* 973824 */
3047 974837, /* 974848 */
3048 975869, /* 975872 */
3049 976883, /* 976896 */
3050 977897, /* 977920 */
3051 978931, /* 978944 */
3052 979949, /* 979968 */
3053 980963, /* 980992 */
3054 981983, /* 982016 */
3055 982981, /* 983040 */
3056 984059, /* 984064 */
3057 985079, /* 985088 */
3058 986101, /* 986112 */
3059 987127, /* 987136 */
3060 988157, /* 988160 */
3061 989173, /* 989184 */
3062 990181, /* 990208 */
3063 991229, /* 991232 */
3064 992249, /* 992256 */
3065 993269, /* 993280 */
3066 994303, /* 994304 */
3067 995327, /* 995328 */
3068 996329, /* 996352 */
3069 997369, /* 997376 */
3070 998399, /* 998400 */
3071 999389, /* 999424 */
3072 1000429, /* 1000448 */
3073 1001467, /* 1001472 */
3074 1002493, /* 1002496 */
3075 1003517, /* 1003520 */
3076 1004537, /* 1004544 */
3077 1005553, /* 1005568 */
3078 1006589, /* 1006592 */
3079 1007609, /* 1007616 */
3080 1008617, /* 1008640 */
3081 1009651, /* 1009664 */
3082 1010687, /* 1010688 */
3083 1011697, /* 1011712 */
3084 1012733, /* 1012736 */
3085 1013741, /* 1013760 */
3086 1014779, /* 1014784 */
3087 1015769, /* 1015808 */
3088 1016789, /* 1016832 */
3089 1017851, /* 1017856 */
3090 1018879, /* 1018880 */
3091 1019903, /* 1019904 */
3092 1020913, /* 1020928 */
3093 1021919, /* 1021952 */
3094 1022963, /* 1022976 */
3095 1023991, /* 1024000 */
3096 1025021, /* 1025024 */
3097 1026043, /* 1026048 */
3098 1027067, /* 1027072 */
3099 1028089, /* 1028096 */
3100 1029113, /* 1029120 */
3101 1030121, /* 1030144 */
3102 1031161, /* 1031168 */
3103 1032191, /* 1032192 */
3104 1033189, /* 1033216 */
3105 1034239, /* 1034240 */
3106 1035263, /* 1035264 */
3107 1036271, /* 1036288 */
3108 1037303, /* 1037312 */
3109 1038329, /* 1038336 */
3110 1039351, /* 1039360 */
3111 1040381, /* 1040384 */
3112 1041373, /* 1041408 */
3113 1042427, /* 1042432 */
3114 1043453, /* 1043456 */
3115 1044479, /* 1044480 */
3116 1045493, /* 1045504 */
3117 1046527, /* 1046528 */
3118 1047551, /* 1047552 */
3119 };
3120 /* 0-128M, increments=102400 */
3121 static
3122 unsigned prime_table3[1024]={
3123 131071, /* 131072 */
3124 262139, /* 262144 */
3125 393209, /* 393216 */
3126 524287, /* 524288 */
3127 655357, /* 655360 */
3128 786431, /* 786432 */
3129 917503, /* 917504 */
3130 1048573, /* 1048576 */
3131 1179641, /* 1179648 */
3132 1310719, /* 1310720 */
3133 1441771, /* 1441792 */
3134 1572853, /* 1572864 */
3135 1703903, /* 1703936 */
3136 1835003, /* 1835008 */
3137 1966079, /* 1966080 */
3138 2097143, /* 2097152 */
3139 2228221, /* 2228224 */
3140 2359267, /* 2359296 */
3141 2490337, /* 2490368 */
3142 2621431, /* 2621440 */
3143 2752499, /* 2752512 */
3144 2883577, /* 2883584 */
3145 3014653, /* 3014656 */
3146 3145721, /* 3145728 */
3147 3276799, /* 3276800 */
3148 3407857, /* 3407872 */
3149 3538933, /* 3538944 */
3150 3670013, /* 3670016 */
3151 3801073, /* 3801088 */
3152 3932153, /* 3932160 */
3153 4063217, /* 4063232 */
3154 4194301, /* 4194304 */
3155 4325359, /* 4325376 */
3156 4456433, /* 4456448 */
3157 4587503, /* 4587520 */
3158 4718579, /* 4718592 */
3159 4849651, /* 4849664 */
3160 4980727, /* 4980736 */
3161 5111791, /* 5111808 */
3162 5242877, /* 5242880 */
3163 5373931, /* 5373952 */
3164 5505023, /* 5505024 */
3165 5636077, /* 5636096 */
3166 5767129, /* 5767168 */
3167 5898209, /* 5898240 */
3168 6029299, /* 6029312 */
3169 6160381, /* 6160384 */
3170 6291449, /* 6291456 */
3171 6422519, /* 6422528 */
3172 6553577, /* 6553600 */
3173 6684659, /* 6684672 */
3174 6815741, /* 6815744 */
3175 6946813, /* 6946816 */
3176 7077883, /* 7077888 */
3177 7208951, /* 7208960 */
3178 7340009, /* 7340032 */
3179 7471099, /* 7471104 */
3180 7602151, /* 7602176 */
3181 7733233, /* 7733248 */
3182 7864301, /* 7864320 */
3183 7995391, /* 7995392 */
3184 8126453, /* 8126464 */
3185 8257531, /* 8257536 */
3186 8388593, /* 8388608 */
3187 8519647, /* 8519680 */
3188 8650727, /* 8650752 */
3189 8781797, /* 8781824 */
3190 8912887, /* 8912896 */
3191 9043967, /* 9043968 */
3192 9175037, /* 9175040 */
3193 9306097, /* 9306112 */
3194 9437179, /* 9437184 */
3195 9568219, /* 9568256 */
3196 9699323, /* 9699328 */
3197 9830393, /* 9830400 */
3198 9961463, /* 9961472 */
3199 10092539, /* 10092544 */
3200 10223593, /* 10223616 */
3201 10354667, /* 10354688 */
3202 10485751, /* 10485760 */
3203 10616831, /* 10616832 */
3204 10747903, /* 10747904 */
3205 10878961, /* 10878976 */
3206 11010037, /* 11010048 */
3207 11141113, /* 11141120 */
3208 11272181, /* 11272192 */
3209 11403247, /* 11403264 */
3210 11534329, /* 11534336 */
3211 11665403, /* 11665408 */
3212 11796469, /* 11796480 */
3213 11927551, /* 11927552 */
3214 12058621, /* 12058624 */
3215 12189677, /* 12189696 */
3216 12320753, /* 12320768 */
3217 12451807, /* 12451840 */
3218 12582893, /* 12582912 */
3219 12713959, /* 12713984 */
3220 12845033, /* 12845056 */
3221 12976121, /* 12976128 */
3222 13107197, /* 13107200 */
3223 13238263, /* 13238272 */
3224 13369333, /* 13369344 */
3225 13500373, /* 13500416 */
3226 13631477, /* 13631488 */
3227 13762549, /* 13762560 */
3228 13893613, /* 13893632 */
3229 14024671, /* 14024704 */
3230 14155763, /* 14155776 */
3231 14286809, /* 14286848 */
3232 14417881, /* 14417920 */
3233 14548979, /* 14548992 */
3234 14680063, /* 14680064 */
3235 14811133, /* 14811136 */
3236 14942197, /* 14942208 */
3237 15073277, /* 15073280 */
3238 15204349, /* 15204352 */
3239 15335407, /* 15335424 */
3240 15466463, /* 15466496 */
3241 15597559, /* 15597568 */
3242 15728611, /* 15728640 */
3243 15859687, /* 15859712 */
3244 15990781, /* 15990784 */
3245 16121849, /* 16121856 */
3246 16252919, /* 16252928 */
3247 16383977, /* 16384000 */
3248 16515067, /* 16515072 */
3249 16646099, /* 16646144 */
3250 16777213, /* 16777216 */
3251 16908263, /* 16908288 */
3252 17039339, /* 17039360 */
3253 17170429, /* 17170432 */
3254 17301463, /* 17301504 */
3255 17432561, /* 17432576 */
3256 17563633, /* 17563648 */
3257 17694709, /* 17694720 */
3258 17825791, /* 17825792 */
3259 17956849, /* 17956864 */
3260 18087899, /* 18087936 */
3261 18219001, /* 18219008 */
3262 18350063, /* 18350080 */
3263 18481097, /* 18481152 */
3264 18612211, /* 18612224 */
3265 18743281, /* 18743296 */
3266 18874367, /* 18874368 */
3267 19005433, /* 19005440 */
3268 19136503, /* 19136512 */
3269 19267561, /* 19267584 */
3270 19398647, /* 19398656 */
3271 19529717, /* 19529728 */
3272 19660799, /* 19660800 */
3273 19791869, /* 19791872 */
3274 19922923, /* 19922944 */
3275 20054011, /* 20054016 */
3276 20185051, /* 20185088 */
3277 20316151, /* 20316160 */
3278 20447191, /* 20447232 */
3279 20578297, /* 20578304 */
3280 20709347, /* 20709376 */
3281 20840429, /* 20840448 */
3282 20971507, /* 20971520 */
3283 21102583, /* 21102592 */
3284 21233651, /* 21233664 */
3285 21364727, /* 21364736 */
3286 21495797, /* 21495808 */
3287 21626819, /* 21626880 */
3288 21757951, /* 21757952 */
3289 21889019, /* 21889024 */
3290 22020091, /* 22020096 */
3291 22151167, /* 22151168 */
3292 22282199, /* 22282240 */
3293 22413289, /* 22413312 */
3294 22544351, /* 22544384 */
3295 22675403, /* 22675456 */
3296 22806521, /* 22806528 */
3297 22937591, /* 22937600 */
3298 23068667, /* 23068672 */
3299 23199731, /* 23199744 */
3300 23330773, /* 23330816 */
3301 23461877, /* 23461888 */
3302 23592937, /* 23592960 */
3303 23724031, /* 23724032 */
3304 23855101, /* 23855104 */
3305 23986159, /* 23986176 */
3306 24117217, /* 24117248 */
3307 24248299, /* 24248320 */
3308 24379391, /* 24379392 */
3309 24510463, /* 24510464 */
3310 24641479, /* 24641536 */
3311 24772603, /* 24772608 */
3312 24903667, /* 24903680 */
3313 25034731, /* 25034752 */
3314 25165813, /* 25165824 */
3315 25296893, /* 25296896 */
3316 25427957, /* 25427968 */
3317 25559033, /* 25559040 */
3318 25690097, /* 25690112 */
3319 25821179, /* 25821184 */
3320 25952243, /* 25952256 */
3321 26083273, /* 26083328 */
3322 26214379, /* 26214400 */
3323 26345471, /* 26345472 */
3324 26476543, /* 26476544 */
3325 26607611, /* 26607616 */
3326 26738687, /* 26738688 */
3327 26869753, /* 26869760 */
3328 27000817, /* 27000832 */
3329 27131903, /* 27131904 */
3330 27262931, /* 27262976 */
3331 27394019, /* 27394048 */
3332 27525109, /* 27525120 */
3333 27656149, /* 27656192 */
3334 27787213, /* 27787264 */
3335 27918323, /* 27918336 */
3336 28049407, /* 28049408 */
3337 28180459, /* 28180480 */
3338 28311541, /* 28311552 */
3339 28442551, /* 28442624 */
3340 28573673, /* 28573696 */
3341 28704749, /* 28704768 */
3342 28835819, /* 28835840 */
3343 28966909, /* 28966912 */
3344 29097977, /* 29097984 */
3345 29229047, /* 29229056 */
3346 29360087, /* 29360128 */
3347 29491193, /* 29491200 */
3348 29622269, /* 29622272 */
3349 29753341, /* 29753344 */
3350 29884411, /* 29884416 */
3351 30015481, /* 30015488 */
3352 30146531, /* 30146560 */
3353 30277627, /* 30277632 */
3354 30408701, /* 30408704 */
3355 30539749, /* 30539776 */
3356 30670847, /* 30670848 */
3357 30801917, /* 30801920 */
3358 30932987, /* 30932992 */
3359 31064063, /* 31064064 */
3360 31195117, /* 31195136 */
3361 31326181, /* 31326208 */
3362 31457269, /* 31457280 */
3363 31588351, /* 31588352 */
3364 31719409, /* 31719424 */
3365 31850491, /* 31850496 */
3366 31981567, /* 31981568 */
3367 32112607, /* 32112640 */
3368 32243707, /* 32243712 */
3369 32374781, /* 32374784 */
3370 32505829, /* 32505856 */
3371 32636921, /* 32636928 */
3372 32767997, /* 32768000 */
3373 32899037, /* 32899072 */
3374 33030121, /* 33030144 */
3375 33161201, /* 33161216 */
3376 33292283, /* 33292288 */
3377 33423319, /* 33423360 */
3378 33554393, /* 33554432 */
3379 33685493, /* 33685504 */
3380 33816571, /* 33816576 */
3381 33947621, /* 33947648 */
3382 34078699, /* 34078720 */
3383 34209787, /* 34209792 */
3384 34340861, /* 34340864 */
3385 34471933, /* 34471936 */
3386 34602991, /* 34603008 */
3387 34734079, /* 34734080 */
3388 34865141, /* 34865152 */
3389 34996223, /* 34996224 */
3390 35127263, /* 35127296 */
3391 35258347, /* 35258368 */
3392 35389423, /* 35389440 */
3393 35520467, /* 35520512 */
3394 35651579, /* 35651584 */
3395 35782613, /* 35782656 */
3396 35913727, /* 35913728 */
3397 36044797, /* 36044800 */
3398 36175871, /* 36175872 */
3399 36306937, /* 36306944 */
3400 36438013, /* 36438016 */
3401 36569083, /* 36569088 */
3402 36700159, /* 36700160 */
3403 36831227, /* 36831232 */
3404 36962291, /* 36962304 */
3405 37093373, /* 37093376 */
3406 37224437, /* 37224448 */
3407 37355503, /* 37355520 */
3408 37486591, /* 37486592 */
3409 37617653, /* 37617664 */
3410 37748717, /* 37748736 */
3411 37879783, /* 37879808 */
3412 38010871, /* 38010880 */
3413 38141951, /* 38141952 */
3414 38273023, /* 38273024 */
3415 38404081, /* 38404096 */
3416 38535151, /* 38535168 */
3417 38666219, /* 38666240 */
3418 38797303, /* 38797312 */
3419 38928371, /* 38928384 */
3420 39059431, /* 39059456 */
3421 39190519, /* 39190528 */
3422 39321599, /* 39321600 */
3423 39452671, /* 39452672 */
3424 39583727, /* 39583744 */
3425 39714799, /* 39714816 */
3426 39845887, /* 39845888 */
3427 39976939, /* 39976960 */
3428 40108027, /* 40108032 */
3429 40239103, /* 40239104 */
3430 40370173, /* 40370176 */
3431 40501231, /* 40501248 */
3432 40632313, /* 40632320 */
3433 40763369, /* 40763392 */
3434 40894457, /* 40894464 */
3435 41025499, /* 41025536 */
3436 41156569, /* 41156608 */
3437 41287651, /* 41287680 */
3438 41418739, /* 41418752 */
3439 41549803, /* 41549824 */
3440 41680871, /* 41680896 */
3441 41811949, /* 41811968 */
3442 41943023, /* 41943040 */
3443 42074101, /* 42074112 */
3444 42205183, /* 42205184 */
3445 42336253, /* 42336256 */
3446 42467317, /* 42467328 */
3447 42598397, /* 42598400 */
3448 42729437, /* 42729472 */
3449 42860537, /* 42860544 */
3450 42991609, /* 42991616 */
3451 43122683, /* 43122688 */
3452 43253759, /* 43253760 */
3453 43384813, /* 43384832 */
3454 43515881, /* 43515904 */
3455 43646963, /* 43646976 */
3456 43778011, /* 43778048 */
3457 43909111, /* 43909120 */
3458 44040187, /* 44040192 */
3459 44171261, /* 44171264 */
3460 44302303, /* 44302336 */
3461 44433391, /* 44433408 */
3462 44564461, /* 44564480 */
3463 44695549, /* 44695552 */
3464 44826611, /* 44826624 */
3465 44957687, /* 44957696 */
3466 45088739, /* 45088768 */
3467 45219827, /* 45219840 */
3468 45350869, /* 45350912 */
3469 45481973, /* 45481984 */
3470 45613039, /* 45613056 */
3471 45744121, /* 45744128 */
3472 45875191, /* 45875200 */
3473 46006249, /* 46006272 */
3474 46137319, /* 46137344 */
3475 46268381, /* 46268416 */
3476 46399471, /* 46399488 */
3477 46530557, /* 46530560 */
3478 46661627, /* 46661632 */
3479 46792699, /* 46792704 */
3480 46923761, /* 46923776 */
3481 47054809, /* 47054848 */
3482 47185907, /* 47185920 */
3483 47316991, /* 47316992 */
3484 47448061, /* 47448064 */
3485 47579131, /* 47579136 */
3486 47710207, /* 47710208 */
3487 47841257, /* 47841280 */
3488 47972341, /* 47972352 */
3489 48103417, /* 48103424 */
3490 48234451, /* 48234496 */
3491 48365563, /* 48365568 */
3492 48496639, /* 48496640 */
3493 48627697, /* 48627712 */
3494 48758783, /* 48758784 */
3495 48889837, /* 48889856 */
3496 49020913, /* 49020928 */
3497 49151987, /* 49152000 */
3498 49283063, /* 49283072 */
3499 49414111, /* 49414144 */
3500 49545193, /* 49545216 */
3501 49676267, /* 49676288 */
3502 49807327, /* 49807360 */
3503 49938431, /* 49938432 */
3504 50069497, /* 50069504 */
3505 50200573, /* 50200576 */
3506 50331599, /* 50331648 */
3507 50462683, /* 50462720 */
3508 50593783, /* 50593792 */
3509 50724859, /* 50724864 */
3510 50855899, /* 50855936 */
3511 50987003, /* 50987008 */
3512 51118069, /* 51118080 */
3513 51249131, /* 51249152 */
3514 51380179, /* 51380224 */
3515 51511277, /* 51511296 */
3516 51642341, /* 51642368 */
3517 51773431, /* 51773440 */
3518 51904511, /* 51904512 */
3519 52035569, /* 52035584 */
3520 52166641, /* 52166656 */
3521 52297717, /* 52297728 */
3522 52428767, /* 52428800 */
3523 52559867, /* 52559872 */
3524 52690919, /* 52690944 */
3525 52821983, /* 52822016 */
3526 52953077, /* 52953088 */
3527 53084147, /* 53084160 */
3528 53215229, /* 53215232 */
3529 53346301, /* 53346304 */
3530 53477357, /* 53477376 */
3531 53608441, /* 53608448 */
3532 53739493, /* 53739520 */
3533 53870573, /* 53870592 */
3534 54001663, /* 54001664 */
3535 54132721, /* 54132736 */
3536 54263789, /* 54263808 */
3537 54394877, /* 54394880 */
3538 54525917, /* 54525952 */
3539 54656983, /* 54657024 */
3540 54788089, /* 54788096 */
3541 54919159, /* 54919168 */
3542 55050217, /* 55050240 */
3543 55181311, /* 55181312 */
3544 55312351, /* 55312384 */
3545 55443433, /* 55443456 */
3546 55574507, /* 55574528 */
3547 55705589, /* 55705600 */
3548 55836659, /* 55836672 */
3549 55967701, /* 55967744 */
3550 56098813, /* 56098816 */
3551 56229881, /* 56229888 */
3552 56360911, /* 56360960 */
3553 56491993, /* 56492032 */
3554 56623093, /* 56623104 */
3555 56754167, /* 56754176 */
3556 56885219, /* 56885248 */
3557 57016319, /* 57016320 */
3558 57147379, /* 57147392 */
3559 57278461, /* 57278464 */
3560 57409529, /* 57409536 */
3561 57540599, /* 57540608 */
3562 57671671, /* 57671680 */
3563 57802739, /* 57802752 */
3564 57933817, /* 57933824 */
3565 58064861, /* 58064896 */
3566 58195939, /* 58195968 */
3567 58327039, /* 58327040 */
3568 58458091, /* 58458112 */
3569 58589161, /* 58589184 */
3570 58720253, /* 58720256 */
3571 58851307, /* 58851328 */
3572 58982389, /* 58982400 */
3573 59113469, /* 59113472 */
3574 59244539, /* 59244544 */
3575 59375587, /* 59375616 */
3576 59506679, /* 59506688 */
3577 59637733, /* 59637760 */
3578 59768831, /* 59768832 */
3579 59899901, /* 59899904 */
3580 60030953, /* 60030976 */
3581 60162029, /* 60162048 */
3582 60293119, /* 60293120 */
3583 60424183, /* 60424192 */
3584 60555227, /* 60555264 */
3585 60686321, /* 60686336 */
3586 60817397, /* 60817408 */
3587 60948479, /* 60948480 */
3588 61079531, /* 61079552 */
3589 61210603, /* 61210624 */
3590 61341659, /* 61341696 */
3591 61472753, /* 61472768 */
3592 61603811, /* 61603840 */
3593 61734899, /* 61734912 */
3594 61865971, /* 61865984 */
3595 61997053, /* 61997056 */
3596 62128127, /* 62128128 */
3597 62259193, /* 62259200 */
3598 62390261, /* 62390272 */
3599 62521331, /* 62521344 */
3600 62652407, /* 62652416 */
3601 62783477, /* 62783488 */
3602 62914549, /* 62914560 */
3603 63045613, /* 63045632 */
3604 63176693, /* 63176704 */
3605 63307763, /* 63307776 */
3606 63438839, /* 63438848 */
3607 63569917, /* 63569920 */
3608 63700991, /* 63700992 */
3609 63832057, /* 63832064 */
3610 63963131, /* 63963136 */
3611 64094207, /* 64094208 */
3612 64225267, /* 64225280 */
3613 64356349, /* 64356352 */
3614 64487417, /* 64487424 */
3615 64618493, /* 64618496 */
3616 64749563, /* 64749568 */
3617 64880587, /* 64880640 */
3618 65011703, /* 65011712 */
3619 65142769, /* 65142784 */
3620 65273851, /* 65273856 */
3621 65404909, /* 65404928 */
3622 65535989, /* 65536000 */
3623 65667067, /* 65667072 */
3624 65798137, /* 65798144 */
3625 65929211, /* 65929216 */
3626 66060277, /* 66060288 */
3627 66191351, /* 66191360 */
3628 66322427, /* 66322432 */
3629 66453479, /* 66453504 */
3630 66584561, /* 66584576 */
3631 66715643, /* 66715648 */
3632 66846709, /* 66846720 */
3633 66977767, /* 66977792 */
3634 67108859, /* 67108864 */
3635 67239883, /* 67239936 */
3636 67370999, /* 67371008 */
3637 67502063, /* 67502080 */
3638 67633127, /* 67633152 */
3639 67764223, /* 67764224 */
3640 67895251, /* 67895296 */
3641 68026363, /* 68026368 */
3642 68157433, /* 68157440 */
3643 68288503, /* 68288512 */
3644 68419567, /* 68419584 */
3645 68550631, /* 68550656 */
3646 68681719, /* 68681728 */
3647 68812769, /* 68812800 */
3648 68943851, /* 68943872 */
3649 69074933, /* 69074944 */
3650 69205987, /* 69206016 */
3651 69337087, /* 69337088 */
3652 69468151, /* 69468160 */
3653 69599221, /* 69599232 */
3654 69730303, /* 69730304 */
3655 69861331, /* 69861376 */
3656 69992443, /* 69992448 */
3657 70123513, /* 70123520 */
3658 70254563, /* 70254592 */
3659 70385641, /* 70385664 */
3660 70516729, /* 70516736 */
3661 70647793, /* 70647808 */
3662 70778861, /* 70778880 */
3663 70909933, /* 70909952 */
3664 71041021, /* 71041024 */
3665 71172091, /* 71172096 */
3666 71303153, /* 71303168 */
3667 71434229, /* 71434240 */
3668 71565283, /* 71565312 */
3669 71696363, /* 71696384 */
3670 71827423, /* 71827456 */
3671 71958521, /* 71958528 */
3672 72089573, /* 72089600 */
3673 72220663, /* 72220672 */
3674 72351733, /* 72351744 */
3675 72482807, /* 72482816 */
3676 72613861, /* 72613888 */
3677 72744937, /* 72744960 */
3678 72876031, /* 72876032 */
3679 73007089, /* 73007104 */
3680 73138171, /* 73138176 */
3681 73269247, /* 73269248 */
3682 73400311, /* 73400320 */
3683 73531379, /* 73531392 */
3684 73662461, /* 73662464 */
3685 73793521, /* 73793536 */
3686 73924583, /* 73924608 */
3687 74055637, /* 74055680 */
3688 74186747, /* 74186752 */
3689 74317801, /* 74317824 */
3690 74448877, /* 74448896 */
3691 74579951, /* 74579968 */
3692 74711027, /* 74711040 */
3693 74842099, /* 74842112 */
3694 74973181, /* 74973184 */
3695 75104243, /* 75104256 */
3696 75235327, /* 75235328 */
3697 75366397, /* 75366400 */
3698 75497467, /* 75497472 */
3699 75628513, /* 75628544 */
3700 75759613, /* 75759616 */
3701 75890653, /* 75890688 */
3702 76021661, /* 76021760 */
3703 76152821, /* 76152832 */
3704 76283897, /* 76283904 */
3705 76414973, /* 76414976 */
3706 76546039, /* 76546048 */
3707 76677113, /* 76677120 */
3708 76808119, /* 76808192 */
3709 76939253, /* 76939264 */
3710 77070317, /* 77070336 */
3711 77201347, /* 77201408 */
3712 77332471, /* 77332480 */
3713 77463541, /* 77463552 */
3714 77594599, /* 77594624 */
3715 77725691, /* 77725696 */
3716 77856767, /* 77856768 */
3717 77987821, /* 77987840 */
3718 78118903, /* 78118912 */
3719 78249973, /* 78249984 */
3720 78381047, /* 78381056 */
3721 78512101, /* 78512128 */
3722 78643199, /* 78643200 */
3723 78774259, /* 78774272 */
3724 78905303, /* 78905344 */
3725 79036411, /* 79036416 */
3726 79167479, /* 79167488 */
3727 79298543, /* 79298560 */
3728 79429619, /* 79429632 */
3729 79560673, /* 79560704 */
3730 79691761, /* 79691776 */
3731 79822829, /* 79822848 */
3732 79953901, /* 79953920 */
3733 80084969, /* 80084992 */
3734 80216063, /* 80216064 */
3735 80347103, /* 80347136 */
3736 80478199, /* 80478208 */
3737 80609279, /* 80609280 */
3738 80740339, /* 80740352 */
3739 80871419, /* 80871424 */
3740 81002489, /* 81002496 */
3741 81133567, /* 81133568 */
3742 81264587, /* 81264640 */
3743 81395683, /* 81395712 */
3744 81526763, /* 81526784 */
3745 81657841, /* 81657856 */
3746 81788923, /* 81788928 */
3747 81919993, /* 81920000 */
3748 82051043, /* 82051072 */
3749 82182137, /* 82182144 */
3750 82313213, /* 82313216 */
3751 82444279, /* 82444288 */
3752 82575331, /* 82575360 */
3753 82706431, /* 82706432 */
3754 82837501, /* 82837504 */
3755 82968563, /* 82968576 */
3756 83099641, /* 83099648 */
3757 83230717, /* 83230720 */
3758 83361781, /* 83361792 */
3759 83492863, /* 83492864 */
3760 83623931, /* 83623936 */
3761 83754997, /* 83755008 */
3762 83886053, /* 83886080 */
3763 84017117, /* 84017152 */
3764 84148213, /* 84148224 */
3765 84279277, /* 84279296 */
3766 84410353, /* 84410368 */
3767 84541421, /* 84541440 */
3768 84672487, /* 84672512 */
3769 84803581, /* 84803584 */
3770 84934621, /* 84934656 */
3771 85065719, /* 85065728 */
3772 85196789, /* 85196800 */
3773 85327849, /* 85327872 */
3774 85458929, /* 85458944 */
3775 85589989, /* 85590016 */
3776 85721081, /* 85721088 */
3777 85852147, /* 85852160 */
3778 85983217, /* 85983232 */
3779 86114279, /* 86114304 */
3780 86245343, /* 86245376 */
3781 86376443, /* 86376448 */
3782 86507507, /* 86507520 */
3783 86638577, /* 86638592 */
3784 86769647, /* 86769664 */
3785 86900731, /* 86900736 */
3786 87031759, /* 87031808 */
3787 87162857, /* 87162880 */
3788 87293939, /* 87293952 */
3789 87425021, /* 87425024 */
3790 87556087, /* 87556096 */
3791 87687167, /* 87687168 */
3792 87818239, /* 87818240 */
3793 87949307, /* 87949312 */
3794 88080359, /* 88080384 */
3795 88211449, /* 88211456 */
3796 88342519, /* 88342528 */
3797 88473569, /* 88473600 */
3798 88604653, /* 88604672 */
3799 88735721, /* 88735744 */
3800 88866797, /* 88866816 */
3801 88997827, /* 88997888 */
3802 89128939, /* 89128960 */
3803 89260027, /* 89260032 */
3804 89391103, /* 89391104 */
3805 89522171, /* 89522176 */
3806 89653217, /* 89653248 */
3807 89784313, /* 89784320 */
3808 89915383, /* 89915392 */
3809 90046441, /* 90046464 */
3810 90177533, /* 90177536 */
3811 90308599, /* 90308608 */
3812 90439667, /* 90439680 */
3813 90570751, /* 90570752 */
3814 90701797, /* 90701824 */
3815 90832871, /* 90832896 */
3816 90963967, /* 90963968 */
3817 91095013, /* 91095040 */
3818 91226101, /* 91226112 */
3819 91357177, /* 91357184 */
3820 91488251, /* 91488256 */
3821 91619321, /* 91619328 */
3822 91750391, /* 91750400 */
3823 91881443, /* 91881472 */
3824 92012537, /* 92012544 */
3825 92143609, /* 92143616 */
3826 92274671, /* 92274688 */
3827 92405723, /* 92405760 */
3828 92536823, /* 92536832 */
3829 92667863, /* 92667904 */
3830 92798969, /* 92798976 */
3831 92930039, /* 92930048 */
3832 93061117, /* 93061120 */
3833 93192191, /* 93192192 */
3834 93323249, /* 93323264 */
3835 93454307, /* 93454336 */
3836 93585379, /* 93585408 */
3837 93716471, /* 93716480 */
3838 93847549, /* 93847552 */
3839 93978559, /* 93978624 */
3840 94109681, /* 94109696 */
3841 94240733, /* 94240768 */
3842 94371833, /* 94371840 */
3843 94502899, /* 94502912 */
3844 94633963, /* 94633984 */
3845 94765039, /* 94765056 */
3846 94896119, /* 94896128 */
3847 95027197, /* 95027200 */
3848 95158249, /* 95158272 */
3849 95289329, /* 95289344 */
3850 95420401, /* 95420416 */
3851 95551487, /* 95551488 */
3852 95682541, /* 95682560 */
3853 95813621, /* 95813632 */
3854 95944691, /* 95944704 */
3855 96075739, /* 96075776 */
3856 96206839, /* 96206848 */
3857 96337919, /* 96337920 */
3858 96468979, /* 96468992 */
3859 96600041, /* 96600064 */
3860 96731101, /* 96731136 */
3861 96862169, /* 96862208 */
3862 96993269, /* 96993280 */
3863 97124347, /* 97124352 */
3864 97255409, /* 97255424 */
3865 97386467, /* 97386496 */
3866 97517543, /* 97517568 */
3867 97648637, /* 97648640 */
3868 97779701, /* 97779712 */
3869 97910759, /* 97910784 */
3870 98041831, /* 98041856 */
3871 98172887, /* 98172928 */
3872 98303999, /* 98304000 */
3873 98435063, /* 98435072 */
3874 98566121, /* 98566144 */
3875 98697187, /* 98697216 */
3876 98828281, /* 98828288 */
3877 98959337, /* 98959360 */
3878 99090427, /* 99090432 */
3879 99221489, /* 99221504 */
3880 99352567, /* 99352576 */
3881 99483647, /* 99483648 */
3882 99614689, /* 99614720 */
3883 99745787, /* 99745792 */
3884 99876851, /* 99876864 */
3885 100007927, /* 100007936 */
3886 100138979, /* 100139008 */
3887 100270069, /* 100270080 */
3888 100401139, /* 100401152 */
3889 100532207, /* 100532224 */
3890 100663291, /* 100663296 */
3891 100794319, /* 100794368 */
3892 100925431, /* 100925440 */
3893 101056507, /* 101056512 */
3894 101187577, /* 101187584 */
3895 101318647, /* 101318656 */
3896 101449717, /* 101449728 */
3897 101580793, /* 101580800 */
3898 101711839, /* 101711872 */
3899 101842931, /* 101842944 */
3900 101974009, /* 101974016 */
3901 102105049, /* 102105088 */
3902 102236149, /* 102236160 */
3903 102367189, /* 102367232 */
3904 102498301, /* 102498304 */
3905 102629369, /* 102629376 */
3906 102760387, /* 102760448 */
3907 102891499, /* 102891520 */
3908 103022537, /* 103022592 */
3909 103153649, /* 103153664 */
3910 103284733, /* 103284736 */
3911 103415791, /* 103415808 */
3912 103546879, /* 103546880 */
3913 103677949, /* 103677952 */
3914 103809011, /* 103809024 */
3915 103940093, /* 103940096 */
3916 104071157, /* 104071168 */
3917 104202233, /* 104202240 */
3918 104333311, /* 104333312 */
3919 104464369, /* 104464384 */
3920 104595397, /* 104595456 */
3921 104726527, /* 104726528 */
3922 104857589, /* 104857600 */
3923 104988641, /* 104988672 */
3924 105119741, /* 105119744 */
3925 105250811, /* 105250816 */
3926 105381841, /* 105381888 */
3927 105512951, /* 105512960 */
3928 105644029, /* 105644032 */
3929 105775079, /* 105775104 */
3930 105906167, /* 105906176 */
3931 106037237, /* 106037248 */
3932 106168319, /* 106168320 */
3933 106299379, /* 106299392 */
3934 106430449, /* 106430464 */
3935 106561523, /* 106561536 */
3936 106692601, /* 106692608 */
3937 106823677, /* 106823680 */
3938 106954747, /* 106954752 */
3939 107085799, /* 107085824 */
3940 107216891, /* 107216896 */
3941 107347943, /* 107347968 */
3942 107479033, /* 107479040 */
3943 107610079, /* 107610112 */
3944 107741167, /* 107741184 */
3945 107872249, /* 107872256 */
3946 108003323, /* 108003328 */
3947 108134393, /* 108134400 */
3948 108265459, /* 108265472 */
3949 108396521, /* 108396544 */
3950 108527603, /* 108527616 */
3951 108658681, /* 108658688 */
3952 108789727, /* 108789760 */
3953 108920831, /* 108920832 */
3954 109051903, /* 109051904 */
3955 109182947, /* 109182976 */
3956 109314043, /* 109314048 */
3957 109445107, /* 109445120 */
3958 109576189, /* 109576192 */
3959 109707253, /* 109707264 */
3960 109838293, /* 109838336 */
3961 109969403, /* 109969408 */
3962 110100409, /* 110100480 */
3963 110231531, /* 110231552 */
3964 110362559, /* 110362624 */
3965 110493661, /* 110493696 */
3966 110624753, /* 110624768 */
3967 110755793, /* 110755840 */
3968 110886883, /* 110886912 */
3969 111017983, /* 111017984 */
3970 111148963, /* 111149056 */
3971 111280121, /* 111280128 */
3972 111411173, /* 111411200 */
3973 111542261, /* 111542272 */
3974 111673343, /* 111673344 */
3975 111804389, /* 111804416 */
3976 111935459, /* 111935488 */
3977 112066553, /* 112066560 */
3978 112197629, /* 112197632 */
3979 112328683, /* 112328704 */
3980 112459751, /* 112459776 */
3981 112590839, /* 112590848 */
3982 112721893, /* 112721920 */
3983 112852981, /* 112852992 */
3984 112984061, /* 112984064 */
3985 113115133, /* 113115136 */
3986 113246183, /* 113246208 */
3987 113377279, /* 113377280 */
3988 113508319, /* 113508352 */
3989 113639419, /* 113639424 */
3990 113770457, /* 113770496 */
3991 113901553, /* 113901568 */
3992 114032599, /* 114032640 */
3993 114163703, /* 114163712 */
3994 114294721, /* 114294784 */
3995 114425807, /* 114425856 */
3996 114556913, /* 114556928 */
3997 114687977, /* 114688000 */
3998 114819031, /* 114819072 */
3999 114950131, /* 114950144 */
4000 115081189, /* 115081216 */
4001 115212287, /* 115212288 */
4002 115343341, /* 115343360 */
4003 115474417, /* 115474432 */
4004 115605467, /* 115605504 */
4005 115736539, /* 115736576 */
4006 115867627, /* 115867648 */
4007 115998719, /* 115998720 */
4008 116129789, /* 116129792 */
4009 116260849, /* 116260864 */
4010 116391917, /* 116391936 */
4011 116523007, /* 116523008 */
4012 116654077, /* 116654080 */
4013 116785133, /* 116785152 */
4014 116916223, /* 116916224 */
4015 117047291, /* 117047296 */
4016 117178367, /* 117178368 */
4017 117309421, /* 117309440 */
4018 117440509, /* 117440512 */
4019 117571523, /* 117571584 */
4020 117702649, /* 117702656 */
4021 117833711, /* 117833728 */
4022 117964793, /* 117964800 */
4023 118095853, /* 118095872 */
4024 118226893, /* 118226944 */
4025 118358003, /* 118358016 */
4026 118489081, /* 118489088 */
4027 118620143, /* 118620160 */
4028 118751207, /* 118751232 */
4029 118882279, /* 118882304 */
4030 119013347, /* 119013376 */
4031 119144447, /* 119144448 */
4032 119275511, /* 119275520 */
4033 119406587, /* 119406592 */
4034 119537653, /* 119537664 */
4035 119668723, /* 119668736 */
4036 119799803, /* 119799808 */
4037 119930873, /* 119930880 */
4038 120061951, /* 120061952 */
4039 120193019, /* 120193024 */
4040 120324077, /* 120324096 */
4041 120455147, /* 120455168 */
4042 120586231, /* 120586240 */
4043 120717307, /* 120717312 */
4044 120848353, /* 120848384 */
4045 120979447, /* 120979456 */
4046 121110523, /* 121110528 */
4047 121241597, /* 121241600 */
4048 121372649, /* 121372672 */
4049 121503737, /* 121503744 */
4050 121634801, /* 121634816 */
4051 121765871, /* 121765888 */
4052 121896949, /* 121896960 */
4053 122028019, /* 122028032 */
4054 122159101, /* 122159104 */
4055 122290171, /* 122290176 */
4056 122421241, /* 122421248 */
4057 122552317, /* 122552320 */
4058 122683391, /* 122683392 */
4059 122814463, /* 122814464 */
4060 122945527, /* 122945536 */
4061 123076601, /* 123076608 */
4062 123207677, /* 123207680 */
4063 123338737, /* 123338752 */
4064 123469783, /* 123469824 */
4065 123600857, /* 123600896 */
4066 123731963, /* 123731968 */
4067 123863023, /* 123863040 */
4068 123994099, /* 123994112 */
4069 124125161, /* 124125184 */
4070 124256243, /* 124256256 */
4071 124387321, /* 124387328 */
4072 124518397, /* 124518400 */
4073 124649449, /* 124649472 */
4074 124780531, /* 124780544 */
4075 124911601, /* 124911616 */
4076 125042663, /* 125042688 */
4077 125173759, /* 125173760 */
4078 125304787, /* 125304832 */
4079 125435897, /* 125435904 */
4080 125566963, /* 125566976 */
4081 125698021, /* 125698048 */
4082 125829103, /* 125829120 */
4083 125960189, /* 125960192 */
4084 126091241, /* 126091264 */
4085 126222293, /* 126222336 */
4086 126353407, /* 126353408 */
4087 126484469, /* 126484480 */
4088 126615551, /* 126615552 */
4089 126746623, /* 126746624 */
4090 126877693, /* 126877696 */
4091 127008733, /* 127008768 */
4092 127139833, /* 127139840 */
4093 127270849, /* 127270912 */
4094 127401947, /* 127401984 */
4095 127533047, /* 127533056 */
4096 127664113, /* 127664128 */
4097 127795181, /* 127795200 */
4098 127926263, /* 127926272 */
4099 128057327, /* 128057344 */
4100 128188409, /* 128188416 */
4101 128319469, /* 128319488 */
4102 128450533, /* 128450560 */
4103 128581631, /* 128581632 */
4104 128712691, /* 128712704 */
4105 128843761, /* 128843776 */
4106 128974841, /* 128974848 */
4107 129105901, /* 129105920 */
4108 129236959, /* 129236992 */
4109 129368051, /* 129368064 */
4110 129499129, /* 129499136 */
4111 129630199, /* 129630208 */
4112 129761273, /* 129761280 */
4113 129892333, /* 129892352 */
4114 130023407, /* 130023424 */
4115 130154483, /* 130154496 */
4116 130285567, /* 130285568 */
4117 130416631, /* 130416640 */
4118 130547621, /* 130547712 */
4119 130678781, /* 130678784 */
4120 130809853, /* 130809856 */
4121 130940911, /* 130940928 */
4122 131071987, /* 131072000 */
4123 131203069, /* 131203072 */
4124 131334131, /* 131334144 */
4125 131465177, /* 131465216 */
4126 131596279, /* 131596288 */
4127 131727359, /* 131727360 */
4128 131858413, /* 131858432 */
4129 131989477, /* 131989504 */
4130 132120557, /* 132120576 */
4131 132251621, /* 132251648 */
4132 132382717, /* 132382720 */
4133 132513781, /* 132513792 */
4134 132644851, /* 132644864 */
4135 132775931, /* 132775936 */
4136 132907007, /* 132907008 */
4137 133038053, /* 133038080 */
4138 133169137, /* 133169152 */
4139 133300207, /* 133300224 */
4140 133431293, /* 133431296 */
4141 133562329, /* 133562368 */
4142 133693433, /* 133693440 */
4143 133824503, /* 133824512 */
4144 133955581, /* 133955584 */
4145 134086639, /* 134086656 */
4146 };
4147
sf_nearest_prime(int n)4148 int sf_nearest_prime( int n )
4149 {
4150 if( n < 0 )
4151 n = -n;
4152
4153 if( n < 8192 )
4154 {
4155 return prime_table0[(n>>3)& 1023];
4156 }
4157 else if( n < 64*1024 )
4158 {
4159 return prime_table1[(n>>6)&1023];
4160 }
4161 else if( n < 1024*1024 )
4162 {
4163 return prime_table2[(n>>10)&1023];
4164 }
4165 else if( n < 128*1024*1024 )
4166 {
4167 return prime_table3[(n>>17)&1023];
4168 }
4169 else if( n < 1024*1024*1024 )
4170 {
4171 return prime_table3[(n>>20)&1023];
4172 }
4173
4174 return 134086639; /* too big for table, just use a big prime */
4175 }
4176
4177