1 /*******************************************************************************
2 This file is part of LibTMCG.
3
4 [CS00] Ronald Cramer, Victor Shoup: 'Signature schemes based on the
5 strong RSA assumption', ACM Transactions on Information and
6 System Security, Vol.3(3), pp. 161--185, 2000
7
8 [RS00] Jean-Francois Raymond, Anton Stiglic: 'Security Issues in the
9 Diffie-Hellman Key Agreement Protocol', ZKS technical report
10 http://citeseer.ist.psu.edu/455251.html
11
12 [HAC] Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone:
13 'Handbook of Applied Cryptography', CRC Press, 1996.
14
15 Copyright (C) 2004, 2005, 2006,
16 2016, 2017, 2018, 2019 Heiko Stamer <HeikoStamer@gmx.net>
17
18 LibTMCG is free software; you can redistribute it and/or modify
19 it under the terms of the GNU General Public License as published by
20 the Free Software Foundation; either version 2 of the License, or
21 (at your option) any later version.
22
23 LibTMCG is distributed in the hope that it will be useful,
24 but WITHOUT ANY WARRANTY; without even the implied warranty of
25 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
26 GNU General Public License for more details.
27
28 You should have received a copy of the GNU General Public License
29 along with LibTMCG; if not, write to the Free Software
30 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
31 *******************************************************************************/
32
33 // include headers
34 #ifdef HAVE_CONFIG_H
35 #include "libTMCG_config.h"
36 #endif
37 #include "mpz_sprime.hh"
38
39 // additional headers
40 #include <cstdio>
41 #include <cassert>
42 #include <iostream>
43 #include <stdexcept>
44 #include "mpz_srandom.hh"
45
46 #define PRIMES 668
47 #define MPRIMES 7836
48 #define SIEVE_SIZE 16
49
50 unsigned long int primes[] = {
51 3, 5, 7, 11, 13, 17, 19, 23,
52 29, 31, 37, 41, 43, 47, 53, 59,
53 61, 67, 71, 73, 79, 83, 89, 97,
54 101, 103, 107, 109, 113, 127, 131, 137,
55 139, 149, 151, 157, 163, 167, 173, 179,
56 181, 191, 193, 197, 199, 211, 223, 227,
57 229, 233, 239, 241, 251, 257, 263, 269,
58 271, 277, 281, 283, 293, 307, 311, 313,
59 317, 331, 337, 347, 349, 353, 359, 367,
60 373, 379, 383, 389, 397, 401, 409, 419,
61 421, 431, 433, 439, 443, 449, 457, 461,
62 463, 467, 479, 487, 491, 499, 503, 509,
63 521, 523, 541, 547, 557, 563, 569, 571,
64 577, 587, 593, 599, 601, 607, 613, 617,
65 619, 631, 641, 643, 647, 653, 659, 661,
66 673, 677, 683, 691, 701, 709, 719, 727,
67 733, 739, 743, 751, 757, 761, 769, 773,
68 787, 797, 809, 811, 821, 823, 827, 829,
69 839, 853, 857, 859, 863, 877, 881, 883,
70 887, 907, 911, 919, 929, 937, 941, 947,
71 953, 967, 971, 977, 983, 991, 997, 1009,
72 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051,
73 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103,
74 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171,
75 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229,
76 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289,
77 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327,
78 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427,
79 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471,
80 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523,
81 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579,
82 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621,
83 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697,
84 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753,
85 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823,
86 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879,
87 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951,
88 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011,
89 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081,
90 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131,
91 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207,
92 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269,
93 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333,
94 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381,
95 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437,
96 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521,
97 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591,
98 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659,
99 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699,
100 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749,
101 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803,
102 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879,
103 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953,
104 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019,
105 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083,
106 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169,
107 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229,
108 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307,
109 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359,
110 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433,
111 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499,
112 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547,
113 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613,
114 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673,
115 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733,
116 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803,
117 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877,
118 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929,
119 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007,
120 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073,
121 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133,
122 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217,
123 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261,
124 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339,
125 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421,
126 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483,
127 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549,
128 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637,
129 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679,
130 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759,
131 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817,
132 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919,
133 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969,
134 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021,
135 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099,
136 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171,
137 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237,
138 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323,
139 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407,
140 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449,
141 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519,
142 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581,
143 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657,
144 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717,
145 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801,
146 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851,
147 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903,
148 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011,
149 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079,
150 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143,
151 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217,
152 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277,
153 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337,
154 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389,
155 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481,
156 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569,
157 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653,
158 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703,
159 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781,
160 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841,
161 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911,
162 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977,
163 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039,
164 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127,
165 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211,
166 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283,
167 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351,
168 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459,
169 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523,
170 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573,
171 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639,
172 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699,
173 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759,
174 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867,
175 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927,
176 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011,
177 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089,
178 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167,
179 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233,
180 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293,
181 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377,
182 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447,
183 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539,
184 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623,
185 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681,
186 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737,
187 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807,
188 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863,
189 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951,
190 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013,
191 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103,
192 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173,
193 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239,
194 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319,
195 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391,
196 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437,
197 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497,
198 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601,
199 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661,
200 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739,
201 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803,
202 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859,
203 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931,
204 9941, 9949, 9967, 9973, 10007, 10009, 10037, 10039,
205 10061, 10067, 10069, 10079, 10091, 10093, 10099, 10103,
206 10111, 10133, 10139, 10141, 10151, 10159, 10163, 10169,
207 10177, 10181, 10193, 10211, 10223, 10243, 10247, 10253,
208 10259, 10267, 10271, 10273, 10289, 10301, 10303, 10313,
209 10321, 10331, 10333, 10337, 10343, 10357, 10369, 10391,
210 10399, 10427, 10429, 10433, 10453, 10457, 10459, 10463,
211 10477, 10487, 10499, 10501, 10513, 10529, 10531, 10559,
212 10567, 10589, 10597, 10601, 10607, 10613, 10627, 10631,
213 10639, 10651, 10657, 10663, 10667, 10687, 10691, 10709,
214 10711, 10723, 10729, 10733, 10739, 10753, 10771, 10781,
215 10789, 10799, 10831, 10837, 10847, 10853, 10859, 10861,
216 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939,
217 10949, 10957, 10973, 10979, 10987, 10993, 11003, 11027,
218 11047, 11057, 11059, 11069, 11071, 11083, 11087, 11093,
219 11113, 11117, 11119, 11131, 11149, 11159, 11161, 11171,
220 11173, 11177, 11197, 11213, 11239, 11243, 11251, 11257,
221 11261, 11273, 11279, 11287, 11299, 11311, 11317, 11321,
222 11329, 11351, 11353, 11369, 11383, 11393, 11399, 11411,
223 11423, 11437, 11443, 11447, 11467, 11471, 11483, 11489,
224 11491, 11497, 11503, 11519, 11527, 11549, 11551, 11579,
225 11587, 11593, 11597, 11617, 11621, 11633, 11657, 11677,
226 11681, 11689, 11699, 11701, 11717, 11719, 11731, 11743,
227 11777, 11779, 11783, 11789, 11801, 11807, 11813, 11821,
228 11827, 11831, 11833, 11839, 11863, 11867, 11887, 11897,
229 11903, 11909, 11923, 11927, 11933, 11939, 11941, 11953,
230 11959, 11969, 11971, 11981, 11987, 12007, 12011, 12037,
231 12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107,
232 12109, 12113, 12119, 12143, 12149, 12157, 12161, 12163,
233 12197, 12203, 12211, 12227, 12239, 12241, 12251, 12253,
234 12263, 12269, 12277, 12281, 12289, 12301, 12323, 12329,
235 12343, 12347, 12373, 12377, 12379, 12391, 12401, 12409,
236 12413, 12421, 12433, 12437, 12451, 12457, 12473, 12479,
237 12487, 12491, 12497, 12503, 12511, 12517, 12527, 12539,
238 12541, 12547, 12553, 12569, 12577, 12583, 12589, 12601,
239 12611, 12613, 12619, 12637, 12641, 12647, 12653, 12659,
240 12671, 12689, 12697, 12703, 12713, 12721, 12739, 12743,
241 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823,
242 12829, 12841, 12853, 12889, 12893, 12899, 12907, 12911,
243 12917, 12919, 12923, 12941, 12953, 12959, 12967, 12973,
244 12979, 12983, 13001, 13003, 13007, 13009, 13033, 13037,
245 13043, 13049, 13063, 13093, 13099, 13103, 13109, 13121,
246 13127, 13147, 13151, 13159, 13163, 13171, 13177, 13183,
247 13187, 13217, 13219, 13229, 13241, 13249, 13259, 13267,
248 13291, 13297, 13309, 13313, 13327, 13331, 13337, 13339,
249 13367, 13381, 13397, 13399, 13411, 13417, 13421, 13441,
250 13451, 13457, 13463, 13469, 13477, 13487, 13499, 13513,
251 13523, 13537, 13553, 13567, 13577, 13591, 13597, 13613,
252 13619, 13627, 13633, 13649, 13669, 13679, 13681, 13687,
253 13691, 13693, 13697, 13709, 13711, 13721, 13723, 13729,
254 13751, 13757, 13759, 13763, 13781, 13789, 13799, 13807,
255 13829, 13831, 13841, 13859, 13873, 13877, 13879, 13883,
256 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963,
257 13967, 13997, 13999, 14009, 14011, 14029, 14033, 14051,
258 14057, 14071, 14081, 14083, 14087, 14107, 14143, 14149,
259 14153, 14159, 14173, 14177, 14197, 14207, 14221, 14243,
260 14249, 14251, 14281, 14293, 14303, 14321, 14323, 14327,
261 14341, 14347, 14369, 14387, 14389, 14401, 14407, 14411,
262 14419, 14423, 14431, 14437, 14447, 14449, 14461, 14479,
263 14489, 14503, 14519, 14533, 14537, 14543, 14549, 14551,
264 14557, 14561, 14563, 14591, 14593, 14621, 14627, 14629,
265 14633, 14639, 14653, 14657, 14669, 14683, 14699, 14713,
266 14717, 14723, 14731, 14737, 14741, 14747, 14753, 14759,
267 14767, 14771, 14779, 14783, 14797, 14813, 14821, 14827,
268 14831, 14843, 14851, 14867, 14869, 14879, 14887, 14891,
269 14897, 14923, 14929, 14939, 14947, 14951, 14957, 14969,
270 14983, 15013, 15017, 15031, 15053, 15061, 15073, 15077,
271 15083, 15091, 15101, 15107, 15121, 15131, 15137, 15139,
272 15149, 15161, 15173, 15187, 15193, 15199, 15217, 15227,
273 15233, 15241, 15259, 15263, 15269, 15271, 15277, 15287,
274 15289, 15299, 15307, 15313, 15319, 15329, 15331, 15349,
275 15359, 15361, 15373, 15377, 15383, 15391, 15401, 15413,
276 15427, 15439, 15443, 15451, 15461, 15467, 15473, 15493,
277 15497, 15511, 15527, 15541, 15551, 15559, 15569, 15581,
278 15583, 15601, 15607, 15619, 15629, 15641, 15643, 15647,
279 15649, 15661, 15667, 15671, 15679, 15683, 15727, 15731,
280 15733, 15737, 15739, 15749, 15761, 15767, 15773, 15787,
281 15791, 15797, 15803, 15809, 15817, 15823, 15859, 15877,
282 15881, 15887, 15889, 15901, 15907, 15913, 15919, 15923,
283 15937, 15959, 15971, 15973, 15991, 16001, 16007, 16033,
284 16057, 16061, 16063, 16067, 16069, 16073, 16087, 16091,
285 16097, 16103, 16111, 16127, 16139, 16141, 16183, 16187,
286 16189, 16193, 16217, 16223, 16229, 16231, 16249, 16253,
287 16267, 16273, 16301, 16319, 16333, 16339, 16349, 16361,
288 16363, 16369, 16381, 16411, 16417, 16421, 16427, 16433,
289 16447, 16451, 16453, 16477, 16481, 16487, 16493, 16519,
290 16529, 16547, 16553, 16561, 16567, 16573, 16603, 16607,
291 16619, 16631, 16633, 16649, 16651, 16657, 16661, 16673,
292 16691, 16693, 16699, 16703, 16729, 16741, 16747, 16759,
293 16763, 16787, 16811, 16823, 16829, 16831, 16843, 16871,
294 16879, 16883, 16889, 16901, 16903, 16921, 16927, 16931,
295 16937, 16943, 16963, 16979, 16981, 16987, 16993, 17011,
296 17021, 17027, 17029, 17033, 17041, 17047, 17053, 17077,
297 17093, 17099, 17107, 17117, 17123, 17137, 17159, 17167,
298 17183, 17189, 17191, 17203, 17207, 17209, 17231, 17239,
299 17257, 17291, 17293, 17299, 17317, 17321, 17327, 17333,
300 17341, 17351, 17359, 17377, 17383, 17387, 17389, 17393,
301 17401, 17417, 17419, 17431, 17443, 17449, 17467, 17471,
302 17477, 17483, 17489, 17491, 17497, 17509, 17519, 17539,
303 17551, 17569, 17573, 17579, 17581, 17597, 17599, 17609,
304 17623, 17627, 17657, 17659, 17669, 17681, 17683, 17707,
305 17713, 17729, 17737, 17747, 17749, 17761, 17783, 17789,
306 17791, 17807, 17827, 17837, 17839, 17851, 17863, 17881,
307 17891, 17903, 17909, 17911, 17921, 17923, 17929, 17939,
308 17957, 17959, 17971, 17977, 17981, 17987, 17989, 18013,
309 18041, 18043, 18047, 18049, 18059, 18061, 18077, 18089,
310 18097, 18119, 18121, 18127, 18131, 18133, 18143, 18149,
311 18169, 18181, 18191, 18199, 18211, 18217, 18223, 18229,
312 18233, 18251, 18253, 18257, 18269, 18287, 18289, 18301,
313 18307, 18311, 18313, 18329, 18341, 18353, 18367, 18371,
314 18379, 18397, 18401, 18413, 18427, 18433, 18439, 18443,
315 18451, 18457, 18461, 18481, 18493, 18503, 18517, 18521,
316 18523, 18539, 18541, 18553, 18583, 18587, 18593, 18617,
317 18637, 18661, 18671, 18679, 18691, 18701, 18713, 18719,
318 18731, 18743, 18749, 18757, 18773, 18787, 18793, 18797,
319 18803, 18839, 18859, 18869, 18899, 18911, 18913, 18917,
320 18919, 18947, 18959, 18973, 18979, 19001, 19009, 19013,
321 19031, 19037, 19051, 19069, 19073, 19079, 19081, 19087,
322 19121, 19139, 19141, 19157, 19163, 19181, 19183, 19207,
323 19211, 19213, 19219, 19231, 19237, 19249, 19259, 19267,
324 19273, 19289, 19301, 19309, 19319, 19333, 19373, 19379,
325 19381, 19387, 19391, 19403, 19417, 19421, 19423, 19427,
326 19429, 19433, 19441, 19447, 19457, 19463, 19469, 19471,
327 19477, 19483, 19489, 19501, 19507, 19531, 19541, 19543,
328 19553, 19559, 19571, 19577, 19583, 19597, 19603, 19609,
329 19661, 19681, 19687, 19697, 19699, 19709, 19717, 19727,
330 19739, 19751, 19753, 19759, 19763, 19777, 19793, 19801,
331 19813, 19819, 19841, 19843, 19853, 19861, 19867, 19889,
332 19891, 19913, 19919, 19927, 19937, 19949, 19961, 19963,
333 19973, 19979, 19991, 19993, 19997, 20011, 20021, 20023,
334 20029, 20047, 20051, 20063, 20071, 20089, 20101, 20107,
335 20113, 20117, 20123, 20129, 20143, 20147, 20149, 20161,
336 20173, 20177, 20183, 20201, 20219, 20231, 20233, 20249,
337 20261, 20269, 20287, 20297, 20323, 20327, 20333, 20341,
338 20347, 20353, 20357, 20359, 20369, 20389, 20393, 20399,
339 20407, 20411, 20431, 20441, 20443, 20477, 20479, 20483,
340 20507, 20509, 20521, 20533, 20543, 20549, 20551, 20563,
341 20593, 20599, 20611, 20627, 20639, 20641, 20663, 20681,
342 20693, 20707, 20717, 20719, 20731, 20743, 20747, 20749,
343 20753, 20759, 20771, 20773, 20789, 20807, 20809, 20849,
344 20857, 20873, 20879, 20887, 20897, 20899, 20903, 20921,
345 20929, 20939, 20947, 20959, 20963, 20981, 20983, 21001,
346 21011, 21013, 21017, 21019, 21023, 21031, 21059, 21061,
347 21067, 21089, 21101, 21107, 21121, 21139, 21143, 21149,
348 21157, 21163, 21169, 21179, 21187, 21191, 21193, 21211,
349 21221, 21227, 21247, 21269, 21277, 21283, 21313, 21317,
350 21319, 21323, 21341, 21347, 21377, 21379, 21383, 21391,
351 21397, 21401, 21407, 21419, 21433, 21467, 21481, 21487,
352 21491, 21493, 21499, 21503, 21517, 21521, 21523, 21529,
353 21557, 21559, 21563, 21569, 21577, 21587, 21589, 21599,
354 21601, 21611, 21613, 21617, 21647, 21649, 21661, 21673,
355 21683, 21701, 21713, 21727, 21737, 21739, 21751, 21757,
356 21767, 21773, 21787, 21799, 21803, 21817, 21821, 21839,
357 21841, 21851, 21859, 21863, 21871, 21881, 21893, 21911,
358 21929, 21937, 21943, 21961, 21977, 21991, 21997, 22003,
359 22013, 22027, 22031, 22037, 22039, 22051, 22063, 22067,
360 22073, 22079, 22091, 22093, 22109, 22111, 22123, 22129,
361 22133, 22147, 22153, 22157, 22159, 22171, 22189, 22193,
362 22229, 22247, 22259, 22271, 22273, 22277, 22279, 22283,
363 22291, 22303, 22307, 22343, 22349, 22367, 22369, 22381,
364 22391, 22397, 22409, 22433, 22441, 22447, 22453, 22469,
365 22481, 22483, 22501, 22511, 22531, 22541, 22543, 22549,
366 22567, 22571, 22573, 22613, 22619, 22621, 22637, 22639,
367 22643, 22651, 22669, 22679, 22691, 22697, 22699, 22709,
368 22717, 22721, 22727, 22739, 22741, 22751, 22769, 22777,
369 22783, 22787, 22807, 22811, 22817, 22853, 22859, 22861,
370 22871, 22877, 22901, 22907, 22921, 22937, 22943, 22961,
371 22963, 22973, 22993, 23003, 23011, 23017, 23021, 23027,
372 23029, 23039, 23041, 23053, 23057, 23059, 23063, 23071,
373 23081, 23087, 23099, 23117, 23131, 23143, 23159, 23167,
374 23173, 23189, 23197, 23201, 23203, 23209, 23227, 23251,
375 23269, 23279, 23291, 23293, 23297, 23311, 23321, 23327,
376 23333, 23339, 23357, 23369, 23371, 23399, 23417, 23431,
377 23447, 23459, 23473, 23497, 23509, 23531, 23537, 23539,
378 23549, 23557, 23561, 23563, 23567, 23581, 23593, 23599,
379 23603, 23609, 23623, 23627, 23629, 23633, 23663, 23669,
380 23671, 23677, 23687, 23689, 23719, 23741, 23743, 23747,
381 23753, 23761, 23767, 23773, 23789, 23801, 23813, 23819,
382 23827, 23831, 23833, 23857, 23869, 23873, 23879, 23887,
383 23893, 23899, 23909, 23911, 23917, 23929, 23957, 23971,
384 23977, 23981, 23993, 24001, 24007, 24019, 24023, 24029,
385 24043, 24049, 24061, 24071, 24077, 24083, 24091, 24097,
386 24103, 24107, 24109, 24113, 24121, 24133, 24137, 24151,
387 24169, 24179, 24181, 24197, 24203, 24223, 24229, 24239,
388 24247, 24251, 24281, 24317, 24329, 24337, 24359, 24371,
389 24373, 24379, 24391, 24407, 24413, 24419, 24421, 24439,
390 24443, 24469, 24473, 24481, 24499, 24509, 24517, 24527,
391 24533, 24547, 24551, 24571, 24593, 24611, 24623, 24631,
392 24659, 24671, 24677, 24683, 24691, 24697, 24709, 24733,
393 24749, 24763, 24767, 24781, 24793, 24799, 24809, 24821,
394 24841, 24847, 24851, 24859, 24877, 24889, 24907, 24917,
395 24919, 24923, 24943, 24953, 24967, 24971, 24977, 24979,
396 24989, 25013, 25031, 25033, 25037, 25057, 25073, 25087,
397 25097, 25111, 25117, 25121, 25127, 25147, 25153, 25163,
398 25169, 25171, 25183, 25189, 25219, 25229, 25237, 25243,
399 25247, 25253, 25261, 25301, 25303, 25307, 25309, 25321,
400 25339, 25343, 25349, 25357, 25367, 25373, 25391, 25409,
401 25411, 25423, 25439, 25447, 25453, 25457, 25463, 25469,
402 25471, 25523, 25537, 25541, 25561, 25577, 25579, 25583,
403 25589, 25601, 25603, 25609, 25621, 25633, 25639, 25643,
404 25657, 25667, 25673, 25679, 25693, 25703, 25717, 25733,
405 25741, 25747, 25759, 25763, 25771, 25793, 25799, 25801,
406 25819, 25841, 25847, 25849, 25867, 25873, 25889, 25903,
407 25913, 25919, 25931, 25933, 25939, 25943, 25951, 25969,
408 25981, 25997, 25999, 26003, 26017, 26021, 26029, 26041,
409 26053, 26083, 26099, 26107, 26111, 26113, 26119, 26141,
410 26153, 26161, 26171, 26177, 26183, 26189, 26203, 26209,
411 26227, 26237, 26249, 26251, 26261, 26263, 26267, 26293,
412 26297, 26309, 26317, 26321, 26339, 26347, 26357, 26371,
413 26387, 26393, 26399, 26407, 26417, 26423, 26431, 26437,
414 26449, 26459, 26479, 26489, 26497, 26501, 26513, 26539,
415 26557, 26561, 26573, 26591, 26597, 26627, 26633, 26641,
416 26647, 26669, 26681, 26683, 26687, 26693, 26699, 26701,
417 26711, 26713, 26717, 26723, 26729, 26731, 26737, 26759,
418 26777, 26783, 26801, 26813, 26821, 26833, 26839, 26849,
419 26861, 26863, 26879, 26881, 26891, 26893, 26903, 26921,
420 26927, 26947, 26951, 26953, 26959, 26981, 26987, 26993,
421 27011, 27017, 27031, 27043, 27059, 27061, 27067, 27073,
422 27077, 27091, 27103, 27107, 27109, 27127, 27143, 27179,
423 27191, 27197, 27211, 27239, 27241, 27253, 27259, 27271,
424 27277, 27281, 27283, 27299, 27329, 27337, 27361, 27367,
425 27397, 27407, 27409, 27427, 27431, 27437, 27449, 27457,
426 27479, 27481, 27487, 27509, 27527, 27529, 27539, 27541,
427 27551, 27581, 27583, 27611, 27617, 27631, 27647, 27653,
428 27673, 27689, 27691, 27697, 27701, 27733, 27737, 27739,
429 27743, 27749, 27751, 27763, 27767, 27773, 27779, 27791,
430 27793, 27799, 27803, 27809, 27817, 27823, 27827, 27847,
431 27851, 27883, 27893, 27901, 27917, 27919, 27941, 27943,
432 27947, 27953, 27961, 27967, 27983, 27997, 28001, 28019,
433 28027, 28031, 28051, 28057, 28069, 28081, 28087, 28097,
434 28099, 28109, 28111, 28123, 28151, 28163, 28181, 28183,
435 28201, 28211, 28219, 28229, 28277, 28279, 28283, 28289,
436 28297, 28307, 28309, 28319, 28349, 28351, 28387, 28393,
437 28403, 28409, 28411, 28429, 28433, 28439, 28447, 28463,
438 28477, 28493, 28499, 28513, 28517, 28537, 28541, 28547,
439 28549, 28559, 28571, 28573, 28579, 28591, 28597, 28603,
440 28607, 28619, 28621, 28627, 28631, 28643, 28649, 28657,
441 28661, 28663, 28669, 28687, 28697, 28703, 28711, 28723,
442 28729, 28751, 28753, 28759, 28771, 28789, 28793, 28807,
443 28813, 28817, 28837, 28843, 28859, 28867, 28871, 28879,
444 28901, 28909, 28921, 28927, 28933, 28949, 28961, 28979,
445 29009, 29017, 29021, 29023, 29027, 29033, 29059, 29063,
446 29077, 29101, 29123, 29129, 29131, 29137, 29147, 29153,
447 29167, 29173, 29179, 29191, 29201, 29207, 29209, 29221,
448 29231, 29243, 29251, 29269, 29287, 29297, 29303, 29311,
449 29327, 29333, 29339, 29347, 29363, 29383, 29387, 29389,
450 29399, 29401, 29411, 29423, 29429, 29437, 29443, 29453,
451 29473, 29483, 29501, 29527, 29531, 29537, 29567, 29569,
452 29573, 29581, 29587, 29599, 29611, 29629, 29633, 29641,
453 29663, 29669, 29671, 29683, 29717, 29723, 29741, 29753,
454 29759, 29761, 29789, 29803, 29819, 29833, 29837, 29851,
455 29863, 29867, 29873, 29879, 29881, 29917, 29921, 29927,
456 29947, 29959, 29983, 29989, 30011, 30013, 30029, 30047,
457 30059, 30071, 30089, 30091, 30097, 30103, 30109, 30113,
458 30119, 30133, 30137, 30139, 30161, 30169, 30181, 30187,
459 30197, 30203, 30211, 30223, 30241, 30253, 30259, 30269,
460 30271, 30293, 30307, 30313, 30319, 30323, 30341, 30347,
461 30367, 30389, 30391, 30403, 30427, 30431, 30449, 30467,
462 30469, 30491, 30493, 30497, 30509, 30517, 30529, 30539,
463 30553, 30557, 30559, 30577, 30593, 30631, 30637, 30643,
464 30649, 30661, 30671, 30677, 30689, 30697, 30703, 30707,
465 30713, 30727, 30757, 30763, 30773, 30781, 30803, 30809,
466 30817, 30829, 30839, 30841, 30851, 30853, 30859, 30869,
467 30871, 30881, 30893, 30911, 30931, 30937, 30941, 30949,
468 30971, 30977, 30983, 31013, 31019, 31033, 31039, 31051,
469 31063, 31069, 31079, 31081, 31091, 31121, 31123, 31139,
470 31147, 31151, 31153, 31159, 31177, 31181, 31183, 31189,
471 31193, 31219, 31223, 31231, 31237, 31247, 31249, 31253,
472 31259, 31267, 31271, 31277, 31307, 31319, 31321, 31327,
473 31333, 31337, 31357, 31379, 31387, 31391, 31393, 31397,
474 31469, 31477, 31481, 31489, 31511, 31513, 31517, 31531,
475 31541, 31543, 31547, 31567, 31573, 31583, 31601, 31607,
476 31627, 31643, 31649, 31657, 31663, 31667, 31687, 31699,
477 31721, 31723, 31727, 31729, 31741, 31751, 31769, 31771,
478 31793, 31799, 31817, 31847, 31849, 31859, 31873, 31883,
479 31891, 31907, 31957, 31963, 31973, 31981, 31991, 32003,
480 32009, 32027, 32029, 32051, 32057, 32059, 32063, 32069,
481 32077, 32083, 32089, 32099, 32117, 32119, 32141, 32143,
482 32159, 32173, 32183, 32189, 32191, 32203, 32213, 32233,
483 32237, 32251, 32257, 32261, 32297, 32299, 32303, 32309,
484 32321, 32323, 32327, 32341, 32353, 32359, 32363, 32369,
485 32371, 32377, 32381, 32401, 32411, 32413, 32423, 32429,
486 32441, 32443, 32467, 32479, 32491, 32497, 32503, 32507,
487 32531, 32533, 32537, 32561, 32563, 32569, 32573, 32579,
488 32587, 32603, 32609, 32611, 32621, 32633, 32647, 32653,
489 32687, 32693, 32707, 32713, 32717, 32719, 32749, 32771,
490 32779, 32783, 32789, 32797, 32801, 32803, 32831, 32833,
491 32839, 32843, 32869, 32887, 32909, 32911, 32917, 32933,
492 32939, 32941, 32957, 32969, 32971, 32983, 32987, 32993,
493 32999, 33013, 33023, 33029, 33037, 33049, 33053, 33071,
494 33073, 33083, 33091, 33107, 33113, 33119, 33149, 33151,
495 33161, 33179, 33181, 33191, 33199, 33203, 33211, 33223,
496 33247, 33287, 33289, 33301, 33311, 33317, 33329, 33331,
497 33343, 33347, 33349, 33353, 33359, 33377, 33391, 33403,
498 33409, 33413, 33427, 33457, 33461, 33469, 33479, 33487,
499 33493, 33503, 33521, 33529, 33533, 33547, 33563, 33569,
500 33577, 33581, 33587, 33589, 33599, 33601, 33613, 33617,
501 33619, 33623, 33629, 33637, 33641, 33647, 33679, 33703,
502 33713, 33721, 33739, 33749, 33751, 33757, 33767, 33769,
503 33773, 33791, 33797, 33809, 33811, 33827, 33829, 33851,
504 33857, 33863, 33871, 33889, 33893, 33911, 33923, 33931,
505 33937, 33941, 33961, 33967, 33997, 34019, 34031, 34033,
506 34039, 34057, 34061, 34123, 34127, 34129, 34141, 34147,
507 34157, 34159, 34171, 34183, 34211, 34213, 34217, 34231,
508 34253, 34259, 34261, 34267, 34273, 34283, 34297, 34301,
509 34303, 34313, 34319, 34327, 34337, 34351, 34361, 34367,
510 34369, 34381, 34403, 34421, 34429, 34439, 34457, 34469,
511 34471, 34483, 34487, 34499, 34501, 34511, 34513, 34519,
512 34537, 34543, 34549, 34583, 34589, 34591, 34603, 34607,
513 34613, 34631, 34649, 34651, 34667, 34673, 34679, 34687,
514 34693, 34703, 34721, 34729, 34739, 34747, 34757, 34759,
515 34763, 34781, 34807, 34819, 34841, 34843, 34847, 34849,
516 34871, 34877, 34883, 34897, 34913, 34919, 34939, 34949,
517 34961, 34963, 34981, 35023, 35027, 35051, 35053, 35059,
518 35069, 35081, 35083, 35089, 35099, 35107, 35111, 35117,
519 35129, 35141, 35149, 35153, 35159, 35171, 35201, 35221,
520 35227, 35251, 35257, 35267, 35279, 35281, 35291, 35311,
521 35317, 35323, 35327, 35339, 35353, 35363, 35381, 35393,
522 35401, 35407, 35419, 35423, 35437, 35447, 35449, 35461,
523 35491, 35507, 35509, 35521, 35527, 35531, 35533, 35537,
524 35543, 35569, 35573, 35591, 35593, 35597, 35603, 35617,
525 35671, 35677, 35729, 35731, 35747, 35753, 35759, 35771,
526 35797, 35801, 35803, 35809, 35831, 35837, 35839, 35851,
527 35863, 35869, 35879, 35897, 35899, 35911, 35923, 35933,
528 35951, 35963, 35969, 35977, 35983, 35993, 35999, 36007,
529 36011, 36013, 36017, 36037, 36061, 36067, 36073, 36083,
530 36097, 36107, 36109, 36131, 36137, 36151, 36161, 36187,
531 36191, 36209, 36217, 36229, 36241, 36251, 36263, 36269,
532 36277, 36293, 36299, 36307, 36313, 36319, 36341, 36343,
533 36353, 36373, 36383, 36389, 36433, 36451, 36457, 36467,
534 36469, 36473, 36479, 36493, 36497, 36523, 36527, 36529,
535 36541, 36551, 36559, 36563, 36571, 36583, 36587, 36599,
536 36607, 36629, 36637, 36643, 36653, 36671, 36677, 36683,
537 36691, 36697, 36709, 36713, 36721, 36739, 36749, 36761,
538 36767, 36779, 36781, 36787, 36791, 36793, 36809, 36821,
539 36833, 36847, 36857, 36871, 36877, 36887, 36899, 36901,
540 36913, 36919, 36923, 36929, 36931, 36943, 36947, 36973,
541 36979, 36997, 37003, 37013, 37019, 37021, 37039, 37049,
542 37057, 37061, 37087, 37097, 37117, 37123, 37139, 37159,
543 37171, 37181, 37189, 37199, 37201, 37217, 37223, 37243,
544 37253, 37273, 37277, 37307, 37309, 37313, 37321, 37337,
545 37339, 37357, 37361, 37363, 37369, 37379, 37397, 37409,
546 37423, 37441, 37447, 37463, 37483, 37489, 37493, 37501,
547 37507, 37511, 37517, 37529, 37537, 37547, 37549, 37561,
548 37567, 37571, 37573, 37579, 37589, 37591, 37607, 37619,
549 37633, 37643, 37649, 37657, 37663, 37691, 37693, 37699,
550 37717, 37747, 37781, 37783, 37799, 37811, 37813, 37831,
551 37847, 37853, 37861, 37871, 37879, 37889, 37897, 37907,
552 37951, 37957, 37963, 37967, 37987, 37991, 37993, 37997,
553 38011, 38039, 38047, 38053, 38069, 38083, 38113, 38119,
554 38149, 38153, 38167, 38177, 38183, 38189, 38197, 38201,
555 38219, 38231, 38237, 38239, 38261, 38273, 38281, 38287,
556 38299, 38303, 38317, 38321, 38327, 38329, 38333, 38351,
557 38371, 38377, 38393, 38431, 38447, 38449, 38453, 38459,
558 38461, 38501, 38543, 38557, 38561, 38567, 38569, 38593,
559 38603, 38609, 38611, 38629, 38639, 38651, 38653, 38669,
560 38671, 38677, 38693, 38699, 38707, 38711, 38713, 38723,
561 38729, 38737, 38747, 38749, 38767, 38783, 38791, 38803,
562 38821, 38833, 38839, 38851, 38861, 38867, 38873, 38891,
563 38903, 38917, 38921, 38923, 38933, 38953, 38959, 38971,
564 38977, 38993, 39019, 39023, 39041, 39043, 39047, 39079,
565 39089, 39097, 39103, 39107, 39113, 39119, 39133, 39139,
566 39157, 39161, 39163, 39181, 39191, 39199, 39209, 39217,
567 39227, 39229, 39233, 39239, 39241, 39251, 39293, 39301,
568 39313, 39317, 39323, 39341, 39343, 39359, 39367, 39371,
569 39373, 39383, 39397, 39409, 39419, 39439, 39443, 39451,
570 39461, 39499, 39503, 39509, 39511, 39521, 39541, 39551,
571 39563, 39569, 39581, 39607, 39619, 39623, 39631, 39659,
572 39667, 39671, 39679, 39703, 39709, 39719, 39727, 39733,
573 39749, 39761, 39769, 39779, 39791, 39799, 39821, 39827,
574 39829, 39839, 39841, 39847, 39857, 39863, 39869, 39877,
575 39883, 39887, 39901, 39929, 39937, 39953, 39971, 39979,
576 39983, 39989, 40009, 40013, 40031, 40037, 40039, 40063,
577 40087, 40093, 40099, 40111, 40123, 40127, 40129, 40151,
578 40153, 40163, 40169, 40177, 40189, 40193, 40213, 40231,
579 40237, 40241, 40253, 40277, 40283, 40289, 40343, 40351,
580 40357, 40361, 40387, 40423, 40427, 40429, 40433, 40459,
581 40471, 40483, 40487, 40493, 40499, 40507, 40519, 40529,
582 40531, 40543, 40559, 40577, 40583, 40591, 40597, 40609,
583 40627, 40637, 40639, 40693, 40697, 40699, 40709, 40739,
584 40751, 40759, 40763, 40771, 40787, 40801, 40813, 40819,
585 40823, 40829, 40841, 40847, 40849, 40853, 40867, 40879,
586 40883, 40897, 40903, 40927, 40933, 40939, 40949, 40961,
587 40973, 40993, 41011, 41017, 41023, 41039, 41047, 41051,
588 41057, 41077, 41081, 41113, 41117, 41131, 41141, 41143,
589 41149, 41161, 41177, 41179, 41183, 41189, 41201, 41203,
590 41213, 41221, 41227, 41231, 41233, 41243, 41257, 41263,
591 41269, 41281, 41299, 41333, 41341, 41351, 41357, 41381,
592 41387, 41389, 41399, 41411, 41413, 41443, 41453, 41467,
593 41479, 41491, 41507, 41513, 41519, 41521, 41539, 41543,
594 41549, 41579, 41593, 41597, 41603, 41609, 41611, 41617,
595 41621, 41627, 41641, 41647, 41651, 41659, 41669, 41681,
596 41687, 41719, 41729, 41737, 41759, 41761, 41771, 41777,
597 41801, 41809, 41813, 41843, 41849, 41851, 41863, 41879,
598 41887, 41893, 41897, 41903, 41911, 41927, 41941, 41947,
599 41953, 41957, 41959, 41969, 41981, 41983, 41999, 42013,
600 42017, 42019, 42023, 42043, 42061, 42071, 42073, 42083,
601 42089, 42101, 42131, 42139, 42157, 42169, 42179, 42181,
602 42187, 42193, 42197, 42209, 42221, 42223, 42227, 42239,
603 42257, 42281, 42283, 42293, 42299, 42307, 42323, 42331,
604 42337, 42349, 42359, 42373, 42379, 42391, 42397, 42403,
605 42407, 42409, 42433, 42437, 42443, 42451, 42457, 42461,
606 42463, 42467, 42473, 42487, 42491, 42499, 42509, 42533,
607 42557, 42569, 42571, 42577, 42589, 42611, 42641, 42643,
608 42649, 42667, 42677, 42683, 42689, 42697, 42701, 42703,
609 42709, 42719, 42727, 42737, 42743, 42751, 42767, 42773,
610 42787, 42793, 42797, 42821, 42829, 42839, 42841, 42853,
611 42859, 42863, 42899, 42901, 42923, 42929, 42937, 42943,
612 42953, 42961, 42967, 42979, 42989, 43003, 43013, 43019,
613 43037, 43049, 43051, 43063, 43067, 43093, 43103, 43117,
614 43133, 43151, 43159, 43177, 43189, 43201, 43207, 43223,
615 43237, 43261, 43271, 43283, 43291, 43313, 43319, 43321,
616 43331, 43391, 43397, 43399, 43403, 43411, 43427, 43441,
617 43451, 43457, 43481, 43487, 43499, 43517, 43541, 43543,
618 43573, 43577, 43579, 43591, 43597, 43607, 43609, 43613,
619 43627, 43633, 43649, 43651, 43661, 43669, 43691, 43711,
620 43717, 43721, 43753, 43759, 43777, 43781, 43783, 43787,
621 43789, 43793, 43801, 43853, 43867, 43889, 43891, 43913,
622 43933, 43943, 43951, 43961, 43963, 43969, 43973, 43987,
623 43991, 43997, 44017, 44021, 44027, 44029, 44041, 44053,
624 44059, 44071, 44087, 44089, 44101, 44111, 44119, 44123,
625 44129, 44131, 44159, 44171, 44179, 44189, 44201, 44203,
626 44207, 44221, 44249, 44257, 44263, 44267, 44269, 44273,
627 44279, 44281, 44293, 44351, 44357, 44371, 44381, 44383,
628 44389, 44417, 44449, 44453, 44483, 44491, 44497, 44501,
629 44507, 44519, 44531, 44533, 44537, 44543, 44549, 44563,
630 44579, 44587, 44617, 44621, 44623, 44633, 44641, 44647,
631 44651, 44657, 44683, 44687, 44699, 44701, 44711, 44729,
632 44741, 44753, 44771, 44773, 44777, 44789, 44797, 44809,
633 44819, 44839, 44843, 44851, 44867, 44879, 44887, 44893,
634 44909, 44917, 44927, 44939, 44953, 44959, 44963, 44971,
635 44983, 44987, 45007, 45013, 45053, 45061, 45077, 45083,
636 45119, 45121, 45127, 45131, 45137, 45139, 45161, 45179,
637 45181, 45191, 45197, 45233, 45247, 45259, 45263, 45281,
638 45289, 45293, 45307, 45317, 45319, 45329, 45337, 45341,
639 45343, 45361, 45377, 45389, 45403, 45413, 45427, 45433,
640 45439, 45481, 45491, 45497, 45503, 45523, 45533, 45541,
641 45553, 45557, 45569, 45587, 45589, 45599, 45613, 45631,
642 45641, 45659, 45667, 45673, 45677, 45691, 45697, 45707,
643 45737, 45751, 45757, 45763, 45767, 45779, 45817, 45821,
644 45823, 45827, 45833, 45841, 45853, 45863, 45869, 45887,
645 45893, 45943, 45949, 45953, 45959, 45971, 45979, 45989,
646 46021, 46027, 46049, 46051, 46061, 46073, 46091, 46093,
647 46099, 46103, 46133, 46141, 46147, 46153, 46171, 46181,
648 46183, 46187, 46199, 46219, 46229, 46237, 46261, 46271,
649 46273, 46279, 46301, 46307, 46309, 46327, 46337, 46349,
650 46351, 46381, 46399, 46411, 46439, 46441, 46447, 46451,
651 46457, 46471, 46477, 46489, 46499, 46507, 46511, 46523,
652 46549, 46559, 46567, 46573, 46589, 46591, 46601, 46619,
653 46633, 46639, 46643, 46649, 46663, 46679, 46681, 46687,
654 46691, 46703, 46723, 46727, 46747, 46751, 46757, 46769,
655 46771, 46807, 46811, 46817, 46819, 46829, 46831, 46853,
656 46861, 46867, 46877, 46889, 46901, 46919, 46933, 46957,
657 46993, 46997, 47017, 47041, 47051, 47057, 47059, 47087,
658 47093, 47111, 47119, 47123, 47129, 47137, 47143, 47147,
659 47149, 47161, 47189, 47207, 47221, 47237, 47251, 47269,
660 47279, 47287, 47293, 47297, 47303, 47309, 47317, 47339,
661 47351, 47353, 47363, 47381, 47387, 47389, 47407, 47417,
662 47419, 47431, 47441, 47459, 47491, 47497, 47501, 47507,
663 47513, 47521, 47527, 47533, 47543, 47563, 47569, 47581,
664 47591, 47599, 47609, 47623, 47629, 47639, 47653, 47657,
665 47659, 47681, 47699, 47701, 47711, 47713, 47717, 47737,
666 47741, 47743, 47777, 47779, 47791, 47797, 47807, 47809,
667 47819, 47837, 47843, 47857, 47869, 47881, 47903, 47911,
668 47917, 47933, 47939, 47947, 47951, 47963, 47969, 47977,
669 47981, 48017, 48023, 48029, 48049, 48073, 48079, 48091,
670 48109, 48119, 48121, 48131, 48157, 48163, 48179, 48187,
671 48193, 48197, 48221, 48239, 48247, 48259, 48271, 48281,
672 48299, 48311, 48313, 48337, 48341, 48353, 48371, 48383,
673 48397, 48407, 48409, 48413, 48437, 48449, 48463, 48473,
674 48479, 48481, 48487, 48491, 48497, 48523, 48527, 48533,
675 48539, 48541, 48563, 48571, 48589, 48593, 48611, 48619,
676 48623, 48647, 48649, 48661, 48673, 48677, 48679, 48731,
677 48733, 48751, 48757, 48761, 48767, 48779, 48781, 48787,
678 48799, 48809, 48817, 48821, 48823, 48847, 48857, 48859,
679 48869, 48871, 48883, 48889, 48907, 48947, 48953, 48973,
680 48989, 48991, 49003, 49009, 49019, 49031, 49033, 49037,
681 49043, 49057, 49069, 49081, 49103, 49109, 49117, 49121,
682 49123, 49139, 49157, 49169, 49171, 49177, 49193, 49199,
683 49201, 49207, 49211, 49223, 49253, 49261, 49277, 49279,
684 49297, 49307, 49331, 49333, 49339, 49363, 49367, 49369,
685 49391, 49393, 49409, 49411, 49417, 49429, 49433, 49451,
686 49459, 49463, 49477, 49481, 49499, 49523, 49529, 49531,
687 49537, 49547, 49549, 49559, 49597, 49603, 49613, 49627,
688 49633, 49639, 49663, 49667, 49669, 49681, 49697, 49711,
689 49727, 49739, 49741, 49747, 49757, 49783, 49787, 49789,
690 49801, 49807, 49811, 49823, 49831, 49843, 49853, 49871,
691 49877, 49891, 49919, 49921, 49927, 49937, 49939, 49943,
692 49957, 49991, 49993, 49999, 50021, 50023, 50033, 50047,
693 50051, 50053, 50069, 50077, 50087, 50093, 50101, 50111,
694 50119, 50123, 50129, 50131, 50147, 50153, 50159, 50177,
695 50207, 50221, 50227, 50231, 50261, 50263, 50273, 50287,
696 50291, 50311, 50321, 50329, 50333, 50341, 50359, 50363,
697 50377, 50383, 50387, 50411, 50417, 50423, 50441, 50459,
698 50461, 50497, 50503, 50513, 50527, 50539, 50543, 50549,
699 50551, 50581, 50587, 50591, 50593, 50599, 50627, 50647,
700 50651, 50671, 50683, 50707, 50723, 50741, 50753, 50767,
701 50773, 50777, 50789, 50821, 50833, 50839, 50849, 50857,
702 50867, 50873, 50891, 50893, 50909, 50923, 50929, 50951,
703 50957, 50969, 50971, 50989, 50993, 51001, 51031, 51043,
704 51047, 51059, 51061, 51071, 51109, 51131, 51133, 51137,
705 51151, 51157, 51169, 51193, 51197, 51199, 51203, 51217,
706 51229, 51239, 51241, 51257, 51263, 51283, 51287, 51307,
707 51329, 51341, 51343, 51347, 51349, 51361, 51383, 51407,
708 51413, 51419, 51421, 51427, 51431, 51437, 51439, 51449,
709 51461, 51473, 51479, 51481, 51487, 51503, 51511, 51517,
710 51521, 51539, 51551, 51563, 51577, 51581, 51593, 51599,
711 51607, 51613, 51631, 51637, 51647, 51659, 51673, 51679,
712 51683, 51691, 51713, 51719, 51721, 51749, 51767, 51769,
713 51787, 51797, 51803, 51817, 51827, 51829, 51839, 51853,
714 51859, 51869, 51871, 51893, 51899, 51907, 51913, 51929,
715 51941, 51949, 51971, 51973, 51977, 51991, 52009, 52021,
716 52027, 52051, 52057, 52067, 52069, 52081, 52103, 52121,
717 52127, 52147, 52153, 52163, 52177, 52181, 52183, 52189,
718 52201, 52223, 52237, 52249, 52253, 52259, 52267, 52289,
719 52291, 52301, 52313, 52321, 52361, 52363, 52369, 52379,
720 52387, 52391, 52433, 52453, 52457, 52489, 52501, 52511,
721 52517, 52529, 52541, 52543, 52553, 52561, 52567, 52571,
722 52579, 52583, 52609, 52627, 52631, 52639, 52667, 52673,
723 52691, 52697, 52709, 52711, 52721, 52727, 52733, 52747,
724 52757, 52769, 52783, 52807, 52813, 52817, 52837, 52859,
725 52861, 52879, 52883, 52889, 52901, 52903, 52919, 52937,
726 52951, 52957, 52963, 52967, 52973, 52981, 52999, 53003,
727 53017, 53047, 53051, 53069, 53077, 53087, 53089, 53093,
728 53101, 53113, 53117, 53129, 53147, 53149, 53161, 53171,
729 53173, 53189, 53197, 53201, 53231, 53233, 53239, 53267,
730 53269, 53279, 53281, 53299, 53309, 53323, 53327, 53353,
731 53359, 53377, 53381, 53401, 53407, 53411, 53419, 53437,
732 53441, 53453, 53479, 53503, 53507, 53527, 53549, 53551,
733 53569, 53591, 53593, 53597, 53609, 53611, 53617, 53623,
734 53629, 53633, 53639, 53653, 53657, 53681, 53693, 53699,
735 53717, 53719, 53731, 53759, 53773, 53777, 53783, 53791,
736 53813, 53819, 53831, 53849, 53857, 53861, 53881, 53887,
737 53891, 53897, 53899, 53917, 53923, 53927, 53939, 53951,
738 53959, 53987, 53993, 54001, 54011, 54013, 54037, 54049,
739 54059, 54083, 54091, 54101, 54121, 54133, 54139, 54151,
740 54163, 54167, 54181, 54193, 54217, 54251, 54269, 54277,
741 54287, 54293, 54311, 54319, 54323, 54331, 54347, 54361,
742 54367, 54371, 54377, 54401, 54403, 54409, 54413, 54419,
743 54421, 54437, 54443, 54449, 54469, 54493, 54497, 54499,
744 54503, 54517, 54521, 54539, 54541, 54547, 54559, 54563,
745 54577, 54581, 54583, 54601, 54617, 54623, 54629, 54631,
746 54647, 54667, 54673, 54679, 54709, 54713, 54721, 54727,
747 54751, 54767, 54773, 54779, 54787, 54799, 54829, 54833,
748 54851, 54869, 54877, 54881, 54907, 54917, 54919, 54941,
749 54949, 54959, 54973, 54979, 54983, 55001, 55009, 55021,
750 55049, 55051, 55057, 55061, 55073, 55079, 55103, 55109,
751 55117, 55127, 55147, 55163, 55171, 55201, 55207, 55213,
752 55217, 55219, 55229, 55243, 55249, 55259, 55291, 55313,
753 55331, 55333, 55337, 55339, 55343, 55351, 55373, 55381,
754 55399, 55411, 55439, 55441, 55457, 55469, 55487, 55501,
755 55511, 55529, 55541, 55547, 55579, 55589, 55603, 55609,
756 55619, 55621, 55631, 55633, 55639, 55661, 55663, 55667,
757 55673, 55681, 55691, 55697, 55711, 55717, 55721, 55733,
758 55763, 55787, 55793, 55799, 55807, 55813, 55817, 55819,
759 55823, 55829, 55837, 55843, 55849, 55871, 55889, 55897,
760 55901, 55903, 55921, 55927, 55931, 55933, 55949, 55967,
761 55987, 55997, 56003, 56009, 56039, 56041, 56053, 56081,
762 56087, 56093, 56099, 56101, 56113, 56123, 56131, 56149,
763 56167, 56171, 56179, 56197, 56207, 56209, 56237, 56239,
764 56249, 56263, 56267, 56269, 56299, 56311, 56333, 56359,
765 56369, 56377, 56383, 56393, 56401, 56417, 56431, 56437,
766 56443, 56453, 56467, 56473, 56477, 56479, 56489, 56501,
767 56503, 56509, 56519, 56527, 56531, 56533, 56543, 56569,
768 56591, 56597, 56599, 56611, 56629, 56633, 56659, 56663,
769 56671, 56681, 56687, 56701, 56711, 56713, 56731, 56737,
770 56747, 56767, 56773, 56779, 56783, 56807, 56809, 56813,
771 56821, 56827, 56843, 56857, 56873, 56891, 56893, 56897,
772 56909, 56911, 56921, 56923, 56929, 56941, 56951, 56957,
773 56963, 56983, 56989, 56993, 56999, 57037, 57041, 57047,
774 57059, 57073, 57077, 57089, 57097, 57107, 57119, 57131,
775 57139, 57143, 57149, 57163, 57173, 57179, 57191, 57193,
776 57203, 57221, 57223, 57241, 57251, 57259, 57269, 57271,
777 57283, 57287, 57301, 57329, 57331, 57347, 57349, 57367,
778 57373, 57383, 57389, 57397, 57413, 57427, 57457, 57467,
779 57487, 57493, 57503, 57527, 57529, 57557, 57559, 57571,
780 57587, 57593, 57601, 57637, 57641, 57649, 57653, 57667,
781 57679, 57689, 57697, 57709, 57713, 57719, 57727, 57731,
782 57737, 57751, 57773, 57781, 57787, 57791, 57793, 57803,
783 57809, 57829, 57839, 57847, 57853, 57859, 57881, 57899,
784 57901, 57917, 57923, 57943, 57947, 57973, 57977, 57991,
785 58013, 58027, 58031, 58043, 58049, 58057, 58061, 58067,
786 58073, 58099, 58109, 58111, 58129, 58147, 58151, 58153,
787 58169, 58171, 58189, 58193, 58199, 58207, 58211, 58217,
788 58229, 58231, 58237, 58243, 58271, 58309, 58313, 58321,
789 58337, 58363, 58367, 58369, 58379, 58391, 58393, 58403,
790 58411, 58417, 58427, 58439, 58441, 58451, 58453, 58477,
791 58481, 58511, 58537, 58543, 58549, 58567, 58573, 58579,
792 58601, 58603, 58613, 58631, 58657, 58661, 58679, 58687,
793 58693, 58699, 58711, 58727, 58733, 58741, 58757, 58763,
794 58771, 58787, 58789, 58831, 58889, 58897, 58901, 58907,
795 58909, 58913, 58921, 58937, 58943, 58963, 58967, 58979,
796 58991, 58997, 59009, 59011, 59021, 59023, 59029, 59051,
797 59053, 59063, 59069, 59077, 59083, 59093, 59107, 59113,
798 59119, 59123, 59141, 59149, 59159, 59167, 59183, 59197,
799 59207, 59209, 59219, 59221, 59233, 59239, 59243, 59263,
800 59273, 59281, 59333, 59341, 59351, 59357, 59359, 59369,
801 59377, 59387, 59393, 59399, 59407, 59417, 59419, 59441,
802 59443, 59447, 59453, 59467, 59471, 59473, 59497, 59509,
803 59513, 59539, 59557, 59561, 59567, 59581, 59611, 59617,
804 59621, 59627, 59629, 59651, 59659, 59663, 59669, 59671,
805 59693, 59699, 59707, 59723, 59729, 59743, 59747, 59753,
806 59771, 59779, 59791, 59797, 59809, 59833, 59863, 59879,
807 59887, 59921, 59929, 59951, 59957, 59971, 59981, 59999,
808 60013, 60017, 60029, 60037, 60041, 60077, 60083, 60089,
809 60091, 60101, 60103, 60107, 60127, 60133, 60139, 60149,
810 60161, 60167, 60169, 60209, 60217, 60223, 60251, 60257,
811 60259, 60271, 60289, 60293, 60317, 60331, 60337, 60343,
812 60353, 60373, 60383, 60397, 60413, 60427, 60443, 60449,
813 60457, 60493, 60497, 60509, 60521, 60527, 60539, 60589,
814 60601, 60607, 60611, 60617, 60623, 60631, 60637, 60647,
815 60649, 60659, 60661, 60679, 60689, 60703, 60719, 60727,
816 60733, 60737, 60757, 60761, 60763, 60773, 60779, 60793,
817 60811, 60821, 60859, 60869, 60887, 60889, 60899, 60901,
818 60913, 60917, 60919, 60923, 60937, 60943, 60953, 60961,
819 61001, 61007, 61027, 61031, 61043, 61051, 61057, 61091,
820 61099, 61121, 61129, 61141, 61151, 61153, 61169, 61211,
821 61223, 61231, 61253, 61261, 61283, 61291, 61297, 61331,
822 61333, 61339, 61343, 61357, 61363, 61379, 61381, 61403,
823 61409, 61417, 61441, 61463, 61469, 61471, 61483, 61487,
824 61493, 61507, 61511, 61519, 61543, 61547, 61553, 61559,
825 61561, 61583, 61603, 61609, 61613, 61627, 61631, 61637,
826 61643, 61651, 61657, 61667, 61673, 61681, 61687, 61703,
827 61717, 61723, 61729, 61751, 61757, 61781, 61813, 61819,
828 61837, 61843, 61861, 61871, 61879, 61909, 61927, 61933,
829 61949, 61961, 61967, 61979, 61981, 61987, 61991, 62003,
830 62011, 62017, 62039, 62047, 62053, 62057, 62071, 62081,
831 62099, 62119, 62129, 62131, 62137, 62141, 62143, 62171,
832 62189, 62191, 62201, 62207, 62213, 62219, 62233, 62273,
833 62297, 62299, 62303, 62311, 62323, 62327, 62347, 62351,
834 62383, 62401, 62417, 62423, 62459, 62467, 62473, 62477,
835 62483, 62497, 62501, 62507, 62533, 62539, 62549, 62563,
836 62581, 62591, 62597, 62603, 62617, 62627, 62633, 62639,
837 62653, 62659, 62683, 62687, 62701, 62723, 62731, 62743,
838 62753, 62761, 62773, 62791, 62801, 62819, 62827, 62851,
839 62861, 62869, 62873, 62897, 62903, 62921, 62927, 62929,
840 62939, 62969, 62971, 62981, 62983, 62987, 62989, 63029,
841 63031, 63059, 63067, 63073, 63079, 63097, 63103, 63113,
842 63127, 63131, 63149, 63179, 63197, 63199, 63211, 63241,
843 63247, 63277, 63281, 63299, 63311, 63313, 63317, 63331,
844 63337, 63347, 63353, 63361, 63367, 63377, 63389, 63391,
845 63397, 63409, 63419, 63421, 63439, 63443, 63463, 63467,
846 63473, 63487, 63493, 63499, 63521, 63527, 63533, 63541,
847 63559, 63577, 63587, 63589, 63599, 63601, 63607, 63611,
848 63617, 63629, 63647, 63649, 63659, 63667, 63671, 63689,
849 63691, 63697, 63703, 63709, 63719, 63727, 63737, 63743,
850 63761, 63773, 63781, 63793, 63799, 63803, 63809, 63823,
851 63839, 63841, 63853, 63857, 63863, 63901, 63907, 63913,
852 63929, 63949, 63977, 63997, 64007, 64013, 64019, 64033,
853 64037, 64063, 64067, 64081, 64091, 64109, 64123, 64151,
854 64153, 64157, 64171, 64187, 64189, 64217, 64223, 64231,
855 64237, 64271, 64279, 64283, 64301, 64303, 64319, 64327,
856 64333, 64373, 64381, 64399, 64403, 64433, 64439, 64451,
857 64453, 64483, 64489, 64499, 64513, 64553, 64567, 64577,
858 64579, 64591, 64601, 64609, 64613, 64621, 64627, 64633,
859 64661, 64663, 64667, 64679, 64693, 64709, 64717, 64747,
860 64763, 64781, 64783, 64793, 64811, 64817, 64849, 64853,
861 64871, 64877, 64879, 64891, 64901, 64919, 64921, 64927,
862 64937, 64951, 64969, 64997, 65003, 65011, 65027, 65029,
863 65033, 65053, 65063, 65071, 65089, 65099, 65101, 65111,
864 65119, 65123, 65129, 65141, 65147, 65167, 65171, 65173,
865 65179, 65183, 65203, 65213, 65239, 65257, 65267, 65269,
866 65287, 65293, 65309, 65323, 65327, 65353, 65357, 65371,
867 65381, 65393, 65407, 65413, 65419, 65423, 65437, 65447,
868 65449, 65479, 65497, 65519, 65521, 65537, 65539, 65543,
869 65551, 65557, 65563, 65579, 65581, 65587, 65599, 65609,
870 65617, 65629, 65633, 65647, 65651, 65657, 65677, 65687,
871 65699, 65701, 65707, 65713, 65717, 65719, 65729, 65731,
872 65761, 65777, 65789, 65809, 65827, 65831, 65837, 65839,
873 65843, 65851, 65867, 65881, 65899, 65921, 65927, 65929,
874 65951, 65957, 65963, 65981, 65983, 65993, 66029, 66037,
875 66041, 66047, 66067, 66071, 66083, 66089, 66103, 66107,
876 66109, 66137, 66161, 66169, 66173, 66179, 66191, 66221,
877 66239, 66271, 66293, 66301, 66337, 66343, 66347, 66359,
878 66361, 66373, 66377, 66383, 66403, 66413, 66431, 66449,
879 66457, 66463, 66467, 66491, 66499, 66509, 66523, 66529,
880 66533, 66541, 66553, 66569, 66571, 66587, 66593, 66601,
881 66617, 66629, 66643, 66653, 66683, 66697, 66701, 66713,
882 66721, 66733, 66739, 66749, 66751, 66763, 66791, 66797,
883 66809, 66821, 66841, 66851, 66853, 66863, 66877, 66883,
884 66889, 66919, 66923, 66931, 66943, 66947, 66949, 66959,
885 66973, 66977, 67003, 67021, 67033, 67043, 67049, 67057,
886 67061, 67073, 67079, 67103, 67121, 67129, 67139, 67141,
887 67153, 67157, 67169, 67181, 67187, 67189, 67211, 67213,
888 67217, 67219, 67231, 67247, 67261, 67271, 67273, 67289,
889 67307, 67339, 67343, 67349, 67369, 67391, 67399, 67409,
890 67411, 67421, 67427, 67429, 67433, 67447, 67453, 67477,
891 67481, 67489, 67493, 67499, 67511, 67523, 67531, 67537,
892 67547, 67559, 67567, 67577, 67579, 67589, 67601, 67607,
893 67619, 67631, 67651, 67679, 67699, 67709, 67723, 67733,
894 67741, 67751, 67757, 67759, 67763, 67777, 67783, 67789,
895 67801, 67807, 67819, 67829, 67843, 67853, 67867, 67883,
896 67891, 67901, 67927, 67931, 67933, 67939, 67943, 67957,
897 67961, 67967, 67979, 67987, 67993, 68023, 68041, 68053,
898 68059, 68071, 68087, 68099, 68111, 68113, 68141, 68147,
899 68161, 68171, 68207, 68209, 68213, 68219, 68227, 68239,
900 68261, 68279, 68281, 68311, 68329, 68351, 68371, 68389,
901 68399, 68437, 68443, 68447, 68449, 68473, 68477, 68483,
902 68489, 68491, 68501, 68507, 68521, 68531, 68539, 68543,
903 68567, 68581, 68597, 68611, 68633, 68639, 68659, 68669,
904 68683, 68687, 68699, 68711, 68713, 68729, 68737, 68743,
905 68749, 68767, 68771, 68777, 68791, 68813, 68819, 68821,
906 68863, 68879, 68881, 68891, 68897, 68899, 68903, 68909,
907 68917, 68927, 68947, 68963, 68993, 69001, 69011, 69019,
908 69029, 69031, 69061, 69067, 69073, 69109, 69119, 69127,
909 69143, 69149, 69151, 69163, 69191, 69193, 69197, 69203,
910 69221, 69233, 69239, 69247, 69257, 69259, 69263, 69313,
911 69317, 69337, 69341, 69371, 69379, 69383, 69389, 69401,
912 69403, 69427, 69431, 69439, 69457, 69463, 69467, 69473,
913 69481, 69491, 69493, 69497, 69499, 69539, 69557, 69593,
914 69623, 69653, 69661, 69677, 69691, 69697, 69709, 69737,
915 69739, 69761, 69763, 69767, 69779, 69809, 69821, 69827,
916 69829, 69833, 69847, 69857, 69859, 69877, 69899, 69911,
917 69929, 69931, 69941, 69959, 69991, 69997, 70001, 70003,
918 70009, 70019, 70039, 70051, 70061, 70067, 70079, 70099,
919 70111, 70117, 70121, 70123, 70139, 70141, 70157, 70163,
920 70177, 70181, 70183, 70199, 70201, 70207, 70223, 70229,
921 70237, 70241, 70249, 70271, 70289, 70297, 70309, 70313,
922 70321, 70327, 70351, 70373, 70379, 70381, 70393, 70423,
923 70429, 70439, 70451, 70457, 70459, 70481, 70487, 70489,
924 70501, 70507, 70529, 70537, 70549, 70571, 70573, 70583,
925 70589, 70607, 70619, 70621, 70627, 70639, 70657, 70663,
926 70667, 70687, 70709, 70717, 70729, 70753, 70769, 70783,
927 70793, 70823, 70841, 70843, 70849, 70853, 70867, 70877,
928 70879, 70891, 70901, 70913, 70919, 70921, 70937, 70949,
929 70951, 70957, 70969, 70979, 70981, 70991, 70997, 70999,
930 71011, 71023, 71039, 71059, 71069, 71081, 71089, 71119,
931 71129, 71143, 71147, 71153, 71161, 71167, 71171, 71191,
932 71209, 71233, 71237, 71249, 71257, 71261, 71263, 71287,
933 71293, 71317, 71327, 71329, 71333, 71339, 71341, 71347,
934 71353, 71359, 71363, 71387, 71389, 71399, 71411, 71413,
935 71419, 71429, 71437, 71443, 71453, 71471, 71473, 71479,
936 71483, 71503, 71527, 71537, 71549, 71551, 71563, 71569,
937 71593, 71597, 71633, 71647, 71663, 71671, 71693, 71699,
938 71707, 71711, 71713, 71719, 71741, 71761, 71777, 71789,
939 71807, 71809, 71821, 71837, 71843, 71849, 71861, 71867,
940 71879, 71881, 71887, 71899, 71909, 71917, 71933, 71941,
941 71947, 71963, 71971, 71983, 71987, 71993, 71999, 72019,
942 72031, 72043, 72047, 72053, 72073, 72077, 72089, 72091,
943 72101, 72103, 72109, 72139, 72161, 72167, 72169, 72173,
944 72211, 72221, 72223, 72227, 72229, 72251, 72253, 72269,
945 72271, 72277, 72287, 72307, 72313, 72337, 72341, 72353,
946 72367, 72379, 72383, 72421, 72431, 72461, 72467, 72469,
947 72481, 72493, 72497, 72503, 72533, 72547, 72551, 72559,
948 72577, 72613, 72617, 72623, 72643, 72647, 72649, 72661,
949 72671, 72673, 72679, 72689, 72701, 72707, 72719, 72727,
950 72733, 72739, 72763, 72767, 72797, 72817, 72823, 72859,
951 72869, 72871, 72883, 72889, 72893, 72901, 72907, 72911,
952 72923, 72931, 72937, 72949, 72953, 72959, 72973, 72977,
953 72997, 73009, 73013, 73019, 73037, 73039, 73043, 73061,
954 73063, 73079, 73091, 73121, 73127, 73133, 73141, 73181,
955 73189, 73237, 73243, 73259, 73277, 73291, 73303, 73309,
956 73327, 73331, 73351, 73361, 73363, 73369, 73379, 73387,
957 73417, 73421, 73433, 73453, 73459, 73471, 73477, 73483,
958 73517, 73523, 73529, 73547, 73553, 73561, 73571, 73583,
959 73589, 73597, 73607, 73609, 73613, 73637, 73643, 73651,
960 73673, 73679, 73681, 73693, 73699, 73709, 73721, 73727,
961 73751, 73757, 73771, 73783, 73819, 73823, 73847, 73849,
962 73859, 73867, 73877, 73883, 73897, 73907, 73939, 73943,
963 73951, 73961, 73973, 73999, 74017, 74021, 74027, 74047,
964 74051, 74071, 74077, 74093, 74099, 74101, 74131, 74143,
965 74149, 74159, 74161, 74167, 74177, 74189, 74197, 74201,
966 74203, 74209, 74219, 74231, 74257, 74279, 74287, 74293,
967 74297, 74311, 74317, 74323, 74353, 74357, 74363, 74377,
968 74381, 74383, 74411, 74413, 74419, 74441, 74449, 74453,
969 74471, 74489, 74507, 74509, 74521, 74527, 74531, 74551,
970 74561, 74567, 74573, 74587, 74597, 74609, 74611, 74623,
971 74653, 74687, 74699, 74707, 74713, 74717, 74719, 74729,
972 74731, 74747, 74759, 74761, 74771, 74779, 74797, 74821,
973 74827, 74831, 74843, 74857, 74861, 74869, 74873, 74887,
974 74891, 74897, 74903, 74923, 74929, 74933, 74941, 74959,
975 75011, 75013, 75017, 75029, 75037, 75041, 75079, 75083,
976 75109, 75133, 75149, 75161, 75167, 75169, 75181, 75193,
977 75209, 75211, 75217, 75223, 75227, 75239, 75253, 75269,
978 75277, 75289, 75307, 75323, 75329, 75337, 75347, 75353,
979 75367, 75377, 75389, 75391, 75401, 75403, 75407, 75431,
980 75437, 75479, 75503, 75511, 75521, 75527, 75533, 75539,
981 75541, 75553, 75557, 75571, 75577, 75583, 75611, 75617,
982 75619, 75629, 75641, 75653, 75659, 75679, 75683, 75689,
983 75703, 75707, 75709, 75721, 75731, 75743, 75767, 75773,
984 75781, 75787, 75793, 75797, 75821, 75833, 75853, 75869,
985 75883, 75913, 75931, 75937, 75941, 75967, 75979, 75983,
986 75989, 75991, 75997, 76001, 76003, 76031, 76039, 76079,
987 76081, 76091, 76099, 76103, 76123, 76129, 76147, 76157,
988 76159, 76163, 76207, 76213, 76231, 76243, 76249, 76253,
989 76259, 76261, 76283, 76289, 76303, 76333, 76343, 76367,
990 76369, 76379, 76387, 76403, 76421, 76423, 76441, 76463,
991 76471, 76481, 76487, 76493, 76507, 76511, 76519, 76537,
992 76541, 76543, 76561, 76579, 76597, 76603, 76607, 76631,
993 76649, 76651, 76667, 76673, 76679, 76697, 76717, 76733,
994 76753, 76757, 76771, 76777, 76781, 76801, 76819, 76829,
995 76831, 76837, 76847, 76871, 76873, 76883, 76907, 76913,
996 76919, 76943, 76949, 76961, 76963, 76991, 77003, 77017,
997 77023, 77029, 77041, 77047, 77069, 77081, 77093, 77101,
998 77137, 77141, 77153, 77167, 77171, 77191, 77201, 77213,
999 77237, 77239, 77243, 77249, 77261, 77263, 77267, 77269,
1000 77279, 77291, 77317, 77323, 77339, 77347, 77351, 77359,
1001 77369, 77377, 77383, 77417, 77419, 77431, 77447, 77471,
1002 77477, 77479, 77489, 77491, 77509, 77513, 77521, 77527,
1003 77543, 77549, 77551, 77557, 77563, 77569, 77573, 77587,
1004 77591, 77611, 77617, 77621, 77641, 77647, 77659, 77681,
1005 77687, 77689, 77699, 77711, 77713, 77719, 77723, 77731,
1006 77743, 77747, 77761, 77773, 77783, 77797, 77801, 77813,
1007 77839, 77849, 77863, 77867, 77893, 77899, 77929, 77933,
1008 77951, 77969, 77977, 77983, 77999, 78007, 78017, 78031,
1009 78041, 78049, 78059, 78079, 78101, 78121, 78137, 78139,
1010 78157, 78163, 78167, 78173, 78179, 78191, 78193, 78203,
1011 78229, 78233, 78241, 78259, 78277, 78283, 78301, 78307,
1012 78311, 78317, 78341, 78347, 78367, 78401, 78427, 78437,
1013 78439, 78467, 78479, 78487, 78497, 78509, 78511, 78517,
1014 78539, 78541, 78553, 78569, 78571, 78577, 78583, 78593,
1015 78607, 78623, 78643, 78649, 78653, 78691, 78697, 78707,
1016 78713, 78721, 78737, 78779, 78781, 78787, 78791, 78797,
1017 78803, 78809, 78823, 78839, 78853, 78857, 78877, 78887,
1018 78889, 78893, 78901, 78919, 78929, 78941, 78977, 78979,
1019 78989, 79031, 79039, 79043, 79063, 79087, 79103, 79111,
1020 79133, 79139, 79147, 79151, 79153, 79159, 79181, 79187,
1021 79193, 79201, 79229, 79231, 79241, 79259, 79273, 79279,
1022 79283, 79301, 79309, 79319, 79333, 79337, 79349, 79357,
1023 79367, 79379, 79393, 79397, 79399, 79411, 79423, 79427,
1024 79433, 79451, 79481, 79493, 79531, 79537, 79549, 79559,
1025 79561, 79579, 79589, 79601, 79609, 79613, 79621, 79627,
1026 79631, 79633, 79657, 79669, 79687, 79691, 79693, 79697,
1027 79699, 79757, 79769, 79777, 79801, 79811, 79813, 79817,
1028 79823, 79829, 79841, 79843, 79847, 79861, 79867, 79873,
1029 79889, 79901, 79903, 79907, 79939, 79943, 79967, 79973,
1030 79979, 79987, 79997, 79999, 0
1031 }; // PRIMES_SIZE = 7836
1032
1033 unsigned long int primes_m1d2[] = {
1034 1, 2, 3, 5, 6, 8, 9, 11,
1035 14, 15, 18, 20, 21, 23, 26, 29,
1036 30, 33, 35, 36, 39, 41, 44, 48,
1037 50, 51, 53, 54, 56, 63, 65, 68,
1038 69, 74, 75, 78, 81, 83, 86, 89,
1039 90, 95, 96, 98, 99, 105, 111, 113,
1040 114, 116, 119, 120, 125, 128, 131, 134,
1041 135, 138, 140, 141, 146, 153, 155, 156,
1042 158, 165, 168, 173, 174, 176, 179, 183,
1043 186, 189, 191, 194, 198, 200, 204, 209,
1044 210, 215, 216, 219, 221, 224, 228, 230,
1045 231, 233, 239, 243, 245, 249, 251, 254,
1046 260, 261, 270, 273, 278, 281, 284, 285,
1047 288, 293, 296, 299, 300, 303, 306, 308,
1048 309, 315, 320, 321, 323, 326, 329, 330,
1049 336, 338, 341, 345, 350, 354, 359, 363,
1050 366, 369, 371, 375, 378, 380, 384, 386,
1051 393, 398, 404, 405, 410, 411, 413, 414,
1052 419, 426, 428, 429, 431, 438, 440, 441,
1053 443, 453, 455, 459, 464, 468, 470, 473,
1054 476, 483, 485, 488, 491, 495, 498, 504,
1055 506, 509, 510, 515, 516, 519, 524, 525,
1056 530, 531, 534, 543, 545, 546, 548, 551,
1057 554, 558, 561, 564, 575, 576, 581, 585,
1058 590, 593, 596, 600, 606, 608, 611, 614,
1059 615, 618, 624, 629, 638, 639, 641, 644,
1060 645, 648, 650, 651, 653, 659, 660, 663,
1061 680, 683, 686, 690, 699, 704, 711, 713,
1062 714, 716, 719, 723, 725, 726, 729, 735,
1063 740, 741, 743, 744, 746, 749, 755, 761,
1064 765, 771, 774, 776, 779, 783, 785, 789,
1065 791, 798, 800, 803, 804, 806, 809, 810,
1066 813, 818, 828, 831, 833, 834, 846, 848,
1067 849, 854, 860, 861, 866, 870, 873, 876,
1068 879, 888, 891, 893, 894, 900, 905, 911,
1069 915, 923, 930, 933, 935, 936, 938, 939,
1070 944, 950, 953, 956, 965, 966, 974, 975,
1071 986, 989, 993, 996, 998, 999, 1001, 1005,
1072 1008, 1013, 1014, 1019, 1026, 1031, 1034, 1040,
1073 1041, 1043, 1044, 1049, 1055, 1056, 1064, 1065,
1074 1068, 1070, 1071, 1076, 1080, 1089, 1101, 1103,
1075 1106, 1110, 1118, 1119, 1121, 1125, 1133, 1134,
1076 1136, 1140, 1143, 1146, 1148, 1154, 1155, 1166,
1077 1169, 1170, 1173, 1175, 1178, 1185, 1188, 1190,
1078 1191, 1194, 1196, 1199, 1205, 1208, 1211, 1218,
1079 1220, 1223, 1229, 1233, 1236, 1238, 1251, 1260,
1080 1265, 1269, 1271, 1274, 1275, 1278, 1289, 1295,
1081 1296, 1304, 1308, 1310, 1316, 1323, 1328, 1329,
1082 1331, 1335, 1338, 1341, 1343, 1344, 1346, 1349,
1083 1353, 1355, 1356, 1359, 1364, 1365, 1370, 1374,
1084 1376, 1383, 1388, 1394, 1395, 1398, 1400, 1401,
1085 1409, 1416, 1418, 1421, 1425, 1428, 1430, 1439,
1086 1443, 1448, 1451, 1454, 1458, 1463, 1469, 1476,
1087 1478, 1481, 1484, 1485, 1499, 1500, 1505, 1509,
1088 1511, 1518, 1520, 1524, 1530, 1533, 1539, 1541,
1089 1544, 1554, 1559, 1560, 1568, 1581, 1583, 1584,
1090 1590, 1593, 1595, 1601, 1604, 1608, 1610, 1614,
1091 1625, 1626, 1628, 1629, 1635, 1649, 1650, 1653,
1092 1656, 1659, 1661, 1664, 1665, 1671, 1673, 1679,
1093 1680, 1685, 1686, 1694, 1695, 1703, 1706, 1716,
1094 1724, 1728, 1730, 1731, 1733, 1734, 1745, 1749,
1095 1755, 1758, 1763, 1764, 1766, 1769, 1770, 1773,
1096 1778, 1779, 1785, 1790, 1791, 1796, 1803, 1806,
1097 1808, 1811, 1815, 1818, 1821, 1829, 1835, 1836,
1098 1838, 1845, 1848, 1850, 1854, 1859, 1863, 1866,
1099 1869, 1880, 1883, 1884, 1889, 1896, 1898, 1901,
1100 1910, 1911, 1916, 1923, 1925, 1926, 1931, 1938,
1101 1940, 1944, 1953, 1955, 1958, 1959, 1961, 1964,
1102 1965, 1971, 1973, 1983, 1994, 2000, 2001, 2003,
1103 2006, 2009, 2010, 2013, 2024, 2025, 2028, 2036,
1104 2039, 2045, 2046, 2049, 2055, 2063, 2064, 2066,
1105 2069, 2076, 2078, 2079, 2088, 2100, 2105, 2108,
1106 2109, 2114, 2115, 2120, 2121, 2126, 2129, 2130,
1107 2135, 2136, 2141, 2144, 2148, 2163, 2168, 2169,
1108 2174, 2178, 2181, 2186, 2195, 2198, 2204, 2210,
1109 2211, 2220, 2223, 2225, 2228, 2231, 2240, 2241,
1110 2246, 2253, 2256, 2258, 2259, 2261, 2273, 2274,
1111 2280, 2283, 2291, 2295, 2298, 2301, 2310, 2318,
1112 2319, 2321, 2324, 2325, 2328, 2331, 2336, 2339,
1113 2345, 2351, 2360, 2361, 2364, 2366, 2375, 2379,
1114 2391, 2393, 2394, 2396, 2399, 2400, 2406, 2408,
1115 2415, 2430, 2435, 2438, 2444, 2451, 2454, 2459,
1116 2465, 2466, 2468, 2471, 2475, 2478, 2483, 2484,
1117 2486, 2493, 2496, 2499, 2501, 2504, 2505, 2510,
1118 2511, 2519, 2525, 2529, 2538, 2540, 2543, 2549,
1119 2550, 2553, 2556, 2559, 2573, 2576, 2583, 2585,
1120 2589, 2594, 2598, 2604, 2613, 2615, 2616, 2618,
1121 2630, 2636, 2639, 2640, 2648, 2651, 2654, 2661,
1122 2666, 2673, 2675, 2690, 2693, 2696, 2699, 2703,
1123 2706, 2708, 2709, 2715, 2718, 2720, 2721, 2724,
1124 2735, 2738, 2739, 2741, 2750, 2751, 2753, 2759,
1125 2760, 2763, 2765, 2778, 2781, 2784, 2786, 2790,
1126 2795, 2811, 2819, 2820, 2823, 2825, 2826, 2828,
1127 2829, 2834, 2841, 2844, 2846, 2850, 2855, 2858,
1128 2868, 2870, 2871, 2874, 2889, 2891, 2895, 2900,
1129 2903, 2906, 2910, 2913, 2919, 2921, 2924, 2925,
1130 2928, 2930, 2933, 2934, 2939, 2940, 2948, 2951,
1131 2961, 2963, 2969, 2976, 2990, 2993, 3003, 3005,
1132 3014, 3018, 3021, 3023, 3026, 3033, 3036, 3039,
1133 3044, 3045, 3050, 3056, 3060, 3065, 3066, 3071,
1134 3075, 3081, 3086, 3098, 3099, 3101, 3105, 3108,
1135 3110, 3114, 3123, 3128, 3131, 3134, 3135, 3138,
1136 3143, 3149, 3150, 3155, 3158, 3161, 3164, 3168,
1137 3171, 3176, 3179, 3180, 3183, 3186, 3189, 3194,
1138 3198, 3210, 3213, 3224, 3225, 3234, 3236, 3240,
1139 3245, 3260, 3264, 3273, 3275, 3276, 3281, 3284,
1140 3285, 3288, 3290, 3299, 3303, 3309, 3318, 3326,
1141 3329, 3330, 3336, 3339, 3344, 3345, 3350, 3351,
1142 3354, 3359, 3366, 3368, 3380, 3381, 3389, 3390,
1143 3395, 3396, 3401, 3411, 3413, 3414, 3416, 3420,
1144 3428, 3431, 3434, 3435, 3441, 3449, 3453, 3455,
1145 3458, 3473, 3474, 3479, 3480, 3483, 3485, 3488,
1146 3491, 3495, 3498, 3500, 3506, 3509, 3513, 3519,
1147 3521, 3528, 3534, 3539, 3551, 3554, 3560, 3563,
1148 3564, 3575, 3579, 3588, 3593, 3596, 3603, 3605,
1149 3606, 3609, 3614, 3618, 3621, 3623, 3626, 3641,
1150 3648, 3653, 3654, 3660, 3665, 3666, 3674, 3675,
1151 3684, 3696, 3705, 3708, 3716, 3725, 3728, 3729,
1152 3738, 3740, 3743, 3744, 3749, 3753, 3758, 3761,
1153 3764, 3768, 3770, 3773, 3774, 3779, 3780, 3786,
1154 3788, 3791, 3794, 3795, 3801, 3803, 3810, 3819,
1155 3821, 3824, 3834, 3836, 3840, 3843, 3845, 3849,
1156 3851, 3858, 3861, 3863, 3870, 3876, 3878, 3879,
1157 3894, 3896, 3908, 3911, 3914, 3920, 3926, 3933,
1158 3936, 3938, 3939, 3941, 3950, 3953, 3959, 3963,
1159 3966, 3968, 3974, 3975, 3981, 3996, 4004, 4005,
1160 4008, 4019, 4026, 4029, 4034, 4040, 4043, 4044,
1161 4046, 4050, 4055, 4058, 4061, 4073, 4080, 4083,
1162 4085, 4089, 4095, 4104, 4109, 4110, 4115, 4116,
1163 4118, 4121, 4131, 4134, 4136, 4143, 4145, 4146,
1164 4148, 4155, 4158, 4164, 4176, 4181, 4184, 4188,
1165 4193, 4194, 4209, 4211, 4214, 4215, 4221, 4223,
1166 4230, 4233, 4250, 4256, 4260, 4263, 4268, 4269,
1167 4271, 4281, 4286, 4290, 4298, 4299, 4304, 4311,
1168 4313, 4314, 4320, 4323, 4331, 4334, 4338, 4340,
1169 4344, 4346, 4349, 4353, 4356, 4359, 4365, 4368,
1170 4370, 4373, 4376, 4380, 4389, 4391, 4401, 4403,
1171 4409, 4410, 4415, 4418, 4419, 4424, 4430, 4431,
1172 4433, 4443, 4446, 4461, 4464, 4466, 4470, 4475,
1173 4481, 4484, 4485, 4499, 4500, 4503, 4505, 4506,
1174 4514, 4520, 4521, 4524, 4529, 4533, 4545, 4551,
1175 4554, 4563, 4566, 4568, 4575, 4578, 4580, 4586,
1176 4590, 4593, 4599, 4601, 4604, 4610, 4613, 4619,
1177 4620, 4628, 4638, 4640, 4641, 4646, 4655, 4659,
1178 4661, 4668, 4670, 4671, 4674, 4685, 4688, 4695,
1179 4698, 4701, 4706, 4709, 4710, 4715, 4716, 4718,
1180 4719, 4730, 4731, 4733, 4736, 4739, 4745, 4748,
1181 4755, 4760, 4766, 4769, 4773, 4775, 4793, 4800,
1182 4806, 4809, 4811, 4814, 4815, 4821, 4824, 4830,
1183 4838, 4839, 4844, 4848, 4859, 4860, 4866, 4869,
1184 4871, 4874, 4883, 4884, 4890, 4893, 4895, 4901,
1185 4905, 4908, 4914, 4916, 4919, 4925, 4928, 4929,
1186 4935, 4941, 4943, 4950, 4953, 4961, 4964, 4965,
1187 4970, 4974, 4983, 4986, 5003, 5004, 5018, 5019,
1188 5030, 5033, 5034, 5039, 5045, 5046, 5049, 5051,
1189 5055, 5066, 5069, 5070, 5075, 5079, 5081, 5084,
1190 5088, 5090, 5096, 5105, 5111, 5121, 5123, 5126,
1191 5129, 5133, 5135, 5136, 5144, 5150, 5151, 5156,
1192 5160, 5165, 5166, 5168, 5171, 5178, 5184, 5195,
1193 5199, 5213, 5214, 5216, 5226, 5228, 5229, 5231,
1194 5238, 5243, 5249, 5250, 5256, 5264, 5265, 5279,
1195 5283, 5294, 5298, 5300, 5303, 5306, 5313, 5315,
1196 5319, 5325, 5328, 5331, 5333, 5343, 5345, 5354,
1197 5355, 5361, 5364, 5366, 5369, 5376, 5385, 5390,
1198 5394, 5399, 5415, 5418, 5423, 5426, 5429, 5430,
1199 5433, 5441, 5444, 5445, 5451, 5454, 5468, 5469,
1200 5474, 5478, 5486, 5489, 5493, 5496, 5501, 5513,
1201 5523, 5528, 5529, 5534, 5535, 5541, 5543, 5546,
1202 5556, 5558, 5559, 5565, 5574, 5579, 5580, 5585,
1203 5586, 5588, 5598, 5606, 5619, 5621, 5625, 5628,
1204 5630, 5636, 5639, 5643, 5649, 5655, 5658, 5660,
1205 5664, 5675, 5676, 5684, 5691, 5696, 5699, 5705,
1206 5711, 5718, 5721, 5723, 5733, 5735, 5741, 5744,
1207 5745, 5748, 5751, 5759, 5763, 5774, 5775, 5789,
1208 5793, 5796, 5798, 5808, 5810, 5816, 5828, 5838,
1209 5840, 5844, 5849, 5850, 5858, 5859, 5865, 5871,
1210 5888, 5889, 5891, 5894, 5900, 5903, 5906, 5910,
1211 5913, 5915, 5916, 5919, 5931, 5933, 5943, 5948,
1212 5951, 5954, 5961, 5963, 5966, 5969, 5970, 5976,
1213 5979, 5984, 5985, 5990, 5993, 6003, 6005, 6018,
1214 6020, 6021, 6024, 6035, 6036, 6048, 6050, 6053,
1215 6054, 6056, 6059, 6071, 6074, 6078, 6080, 6081,
1216 6098, 6101, 6105, 6113, 6119, 6120, 6125, 6126,
1217 6131, 6134, 6138, 6140, 6144, 6150, 6161, 6164,
1218 6171, 6173, 6186, 6188, 6189, 6195, 6200, 6204,
1219 6206, 6210, 6216, 6218, 6225, 6228, 6236, 6239,
1220 6243, 6245, 6248, 6251, 6255, 6258, 6263, 6269,
1221 6270, 6273, 6276, 6284, 6288, 6291, 6294, 6300,
1222 6305, 6306, 6309, 6318, 6320, 6323, 6326, 6329,
1223 6335, 6344, 6348, 6351, 6356, 6360, 6369, 6371,
1224 6378, 6381, 6390, 6395, 6399, 6404, 6410, 6411,
1225 6414, 6420, 6426, 6444, 6446, 6449, 6453, 6455,
1226 6458, 6459, 6461, 6470, 6476, 6479, 6483, 6486,
1227 6489, 6491, 6500, 6501, 6503, 6504, 6516, 6518,
1228 6521, 6524, 6531, 6546, 6549, 6551, 6554, 6560,
1229 6563, 6573, 6575, 6579, 6581, 6585, 6588, 6591,
1230 6593, 6608, 6609, 6614, 6620, 6624, 6629, 6633,
1231 6645, 6648, 6654, 6656, 6663, 6665, 6668, 6669,
1232 6683, 6690, 6698, 6699, 6705, 6708, 6710, 6720,
1233 6725, 6728, 6731, 6734, 6738, 6743, 6749, 6756,
1234 6761, 6768, 6776, 6783, 6788, 6795, 6798, 6806,
1235 6809, 6813, 6816, 6824, 6834, 6839, 6840, 6843,
1236 6845, 6846, 6848, 6854, 6855, 6860, 6861, 6864,
1237 6875, 6878, 6879, 6881, 6890, 6894, 6899, 6903,
1238 6914, 6915, 6920, 6929, 6936, 6938, 6939, 6941,
1239 6950, 6951, 6953, 6956, 6960, 6965, 6966, 6981,
1240 6983, 6998, 6999, 7004, 7005, 7014, 7016, 7025,
1241 7028, 7035, 7040, 7041, 7043, 7053, 7071, 7074,
1242 7076, 7079, 7086, 7088, 7098, 7103, 7110, 7121,
1243 7124, 7125, 7140, 7146, 7151, 7160, 7161, 7163,
1244 7170, 7173, 7184, 7193, 7194, 7200, 7203, 7205,
1245 7209, 7211, 7215, 7218, 7223, 7224, 7230, 7239,
1246 7244, 7251, 7259, 7266, 7268, 7271, 7274, 7275,
1247 7278, 7280, 7281, 7295, 7296, 7310, 7313, 7314,
1248 7316, 7319, 7326, 7328, 7334, 7341, 7349, 7356,
1249 7358, 7361, 7365, 7368, 7370, 7373, 7376, 7379,
1250 7383, 7385, 7389, 7391, 7398, 7406, 7410, 7413,
1251 7415, 7421, 7425, 7433, 7434, 7439, 7443, 7445,
1252 7448, 7461, 7464, 7469, 7473, 7475, 7478, 7484,
1253 7491, 7506, 7508, 7515, 7526, 7530, 7536, 7538,
1254 7541, 7545, 7550, 7553, 7560, 7565, 7568, 7569,
1255 7574, 7580, 7586, 7593, 7596, 7599, 7608, 7613,
1256 7616, 7620, 7629, 7631, 7634, 7635, 7638, 7643,
1257 7644, 7649, 7653, 7656, 7659, 7664, 7665, 7674,
1258 7679, 7680, 7686, 7688, 7691, 7695, 7700, 7706,
1259 7713, 7719, 7721, 7725, 7730, 7733, 7736, 7746,
1260 7748, 7755, 7763, 7770, 7775, 7779, 7784, 7790,
1261 7791, 7800, 7803, 7809, 7814, 7820, 7821, 7823,
1262 7824, 7830, 7833, 7835, 7839, 7841, 7863, 7865,
1263 7866, 7868, 7869, 7874, 7880, 7883, 7886, 7893,
1264 7895, 7898, 7901, 7904, 7908, 7911, 7929, 7938,
1265 7940, 7943, 7944, 7950, 7953, 7956, 7959, 7961,
1266 7968, 7979, 7985, 7986, 7995, 8000, 8003, 8016,
1267 8028, 8030, 8031, 8033, 8034, 8036, 8043, 8045,
1268 8048, 8051, 8055, 8063, 8069, 8070, 8091, 8093,
1269 8094, 8096, 8108, 8111, 8114, 8115, 8124, 8126,
1270 8133, 8136, 8150, 8159, 8166, 8169, 8174, 8180,
1271 8181, 8184, 8190, 8205, 8208, 8210, 8213, 8216,
1272 8223, 8225, 8226, 8238, 8240, 8243, 8246, 8259,
1273 8264, 8273, 8276, 8280, 8283, 8286, 8301, 8303,
1274 8309, 8315, 8316, 8324, 8325, 8328, 8330, 8336,
1275 8345, 8346, 8349, 8351, 8364, 8370, 8373, 8379,
1276 8381, 8393, 8405, 8411, 8414, 8415, 8421, 8435,
1277 8439, 8441, 8444, 8450, 8451, 8460, 8463, 8465,
1278 8468, 8471, 8481, 8489, 8490, 8493, 8496, 8505,
1279 8510, 8513, 8514, 8516, 8520, 8523, 8526, 8538,
1280 8546, 8549, 8553, 8558, 8561, 8568, 8579, 8583,
1281 8591, 8594, 8595, 8601, 8603, 8604, 8615, 8619,
1282 8628, 8645, 8646, 8649, 8658, 8660, 8663, 8666,
1283 8670, 8675, 8679, 8688, 8691, 8693, 8694, 8696,
1284 8700, 8708, 8709, 8715, 8721, 8724, 8733, 8735,
1285 8738, 8741, 8744, 8745, 8748, 8754, 8759, 8769,
1286 8775, 8784, 8786, 8789, 8790, 8798, 8799, 8804,
1287 8811, 8813, 8828, 8829, 8834, 8840, 8841, 8853,
1288 8856, 8864, 8868, 8873, 8874, 8880, 8891, 8894,
1289 8895, 8903, 8913, 8918, 8919, 8925, 8931, 8940,
1290 8945, 8951, 8954, 8955, 8960, 8961, 8964, 8969,
1291 8978, 8979, 8985, 8988, 8990, 8993, 8994, 9006,
1292 9020, 9021, 9023, 9024, 9029, 9030, 9038, 9044,
1293 9048, 9059, 9060, 9063, 9065, 9066, 9071, 9074,
1294 9084, 9090, 9095, 9099, 9105, 9108, 9111, 9114,
1295 9116, 9125, 9126, 9128, 9134, 9143, 9144, 9150,
1296 9153, 9155, 9156, 9164, 9170, 9176, 9183, 9185,
1297 9189, 9198, 9200, 9206, 9213, 9216, 9219, 9221,
1298 9225, 9228, 9230, 9240, 9246, 9251, 9258, 9260,
1299 9261, 9269, 9270, 9276, 9291, 9293, 9296, 9308,
1300 9318, 9330, 9335, 9339, 9345, 9350, 9356, 9359,
1301 9365, 9371, 9374, 9378, 9386, 9393, 9396, 9398,
1302 9401, 9419, 9429, 9434, 9449, 9455, 9456, 9458,
1303 9459, 9473, 9479, 9486, 9489, 9500, 9504, 9506,
1304 9515, 9518, 9525, 9534, 9536, 9539, 9540, 9543,
1305 9560, 9569, 9570, 9578, 9581, 9590, 9591, 9603,
1306 9605, 9606, 9609, 9615, 9618, 9624, 9629, 9633,
1307 9636, 9644, 9650, 9654, 9659, 9666, 9686, 9689,
1308 9690, 9693, 9695, 9701, 9708, 9710, 9711, 9713,
1309 9714, 9716, 9720, 9723, 9728, 9731, 9734, 9735,
1310 9738, 9741, 9744, 9750, 9753, 9765, 9770, 9771,
1311 9776, 9779, 9785, 9788, 9791, 9798, 9801, 9804,
1312 9830, 9840, 9843, 9848, 9849, 9854, 9858, 9863,
1313 9869, 9875, 9876, 9879, 9881, 9888, 9896, 9900,
1314 9906, 9909, 9920, 9921, 9926, 9930, 9933, 9944,
1315 9945, 9956, 9959, 9963, 9968, 9974, 9980, 9981,
1316 9986, 9989, 9995, 9996, 9998, 10005, 10010, 10011,
1317 10014, 10023, 10025, 10031, 10035, 10044, 10050, 10053,
1318 10056, 10058, 10061, 10064, 10071, 10073, 10074, 10080,
1319 10086, 10088, 10091, 10100, 10109, 10115, 10116, 10124,
1320 10130, 10134, 10143, 10148, 10161, 10163, 10166, 10170,
1321 10173, 10176, 10178, 10179, 10184, 10194, 10196, 10199,
1322 10203, 10205, 10215, 10220, 10221, 10238, 10239, 10241,
1323 10253, 10254, 10260, 10266, 10271, 10274, 10275, 10281,
1324 10296, 10299, 10305, 10313, 10319, 10320, 10331, 10340,
1325 10346, 10353, 10358, 10359, 10365, 10371, 10373, 10374,
1326 10376, 10379, 10385, 10386, 10394, 10403, 10404, 10424,
1327 10428, 10436, 10439, 10443, 10448, 10449, 10451, 10460,
1328 10464, 10469, 10473, 10479, 10481, 10490, 10491, 10500,
1329 10505, 10506, 10508, 10509, 10511, 10515, 10529, 10530,
1330 10533, 10544, 10550, 10553, 10560, 10569, 10571, 10574,
1331 10578, 10581, 10584, 10589, 10593, 10595, 10596, 10605,
1332 10610, 10613, 10623, 10634, 10638, 10641, 10656, 10658,
1333 10659, 10661, 10670, 10673, 10688, 10689, 10691, 10695,
1334 10698, 10700, 10703, 10709, 10716, 10733, 10740, 10743,
1335 10745, 10746, 10749, 10751, 10758, 10760, 10761, 10764,
1336 10778, 10779, 10781, 10784, 10788, 10793, 10794, 10799,
1337 10800, 10805, 10806, 10808, 10823, 10824, 10830, 10836,
1338 10841, 10850, 10856, 10863, 10868, 10869, 10875, 10878,
1339 10883, 10886, 10893, 10899, 10901, 10908, 10910, 10919,
1340 10920, 10925, 10929, 10931, 10935, 10940, 10946, 10955,
1341 10964, 10968, 10971, 10980, 10988, 10995, 10998, 11001,
1342 11006, 11013, 11015, 11018, 11019, 11025, 11031, 11033,
1343 11036, 11039, 11045, 11046, 11054, 11055, 11061, 11064,
1344 11066, 11073, 11076, 11078, 11079, 11085, 11094, 11096,
1345 11114, 11123, 11129, 11135, 11136, 11138, 11139, 11141,
1346 11145, 11151, 11153, 11171, 11174, 11183, 11184, 11190,
1347 11195, 11198, 11204, 11216, 11220, 11223, 11226, 11234,
1348 11240, 11241, 11250, 11255, 11265, 11270, 11271, 11274,
1349 11283, 11285, 11286, 11306, 11309, 11310, 11318, 11319,
1350 11321, 11325, 11334, 11339, 11345, 11348, 11349, 11354,
1351 11358, 11360, 11363, 11369, 11370, 11375, 11384, 11388,
1352 11391, 11393, 11403, 11405, 11408, 11426, 11429, 11430,
1353 11435, 11438, 11450, 11453, 11460, 11468, 11471, 11480,
1354 11481, 11486, 11496, 11501, 11505, 11508, 11510, 11513,
1355 11514, 11519, 11520, 11526, 11528, 11529, 11531, 11535,
1356 11540, 11543, 11549, 11558, 11565, 11571, 11579, 11583,
1357 11586, 11594, 11598, 11600, 11601, 11604, 11613, 11625,
1358 11634, 11639, 11645, 11646, 11648, 11655, 11660, 11663,
1359 11666, 11669, 11678, 11684, 11685, 11699, 11708, 11715,
1360 11723, 11729, 11736, 11748, 11754, 11765, 11768, 11769,
1361 11774, 11778, 11780, 11781, 11783, 11790, 11796, 11799,
1362 11801, 11804, 11811, 11813, 11814, 11816, 11831, 11834,
1363 11835, 11838, 11843, 11844, 11859, 11870, 11871, 11873,
1364 11876, 11880, 11883, 11886, 11894, 11900, 11906, 11909,
1365 11913, 11915, 11916, 11928, 11934, 11936, 11939, 11943,
1366 11946, 11949, 11954, 11955, 11958, 11964, 11978, 11985,
1367 11988, 11990, 11996, 12000, 12003, 12009, 12011, 12014,
1368 12021, 12024, 12030, 12035, 12038, 12041, 12045, 12048,
1369 12051, 12053, 12054, 12056, 12060, 12066, 12068, 12075,
1370 12084, 12089, 12090, 12098, 12101, 12111, 12114, 12119,
1371 12123, 12125, 12140, 12158, 12164, 12168, 12179, 12185,
1372 12186, 12189, 12195, 12203, 12206, 12209, 12210, 12219,
1373 12221, 12234, 12236, 12240, 12249, 12254, 12258, 12263,
1374 12266, 12273, 12275, 12285, 12296, 12305, 12311, 12315,
1375 12329, 12335, 12338, 12341, 12345, 12348, 12354, 12366,
1376 12374, 12381, 12383, 12390, 12396, 12399, 12404, 12410,
1377 12420, 12423, 12425, 12429, 12438, 12444, 12453, 12458,
1378 12459, 12461, 12471, 12476, 12483, 12485, 12488, 12489,
1379 12494, 12506, 12515, 12516, 12518, 12528, 12536, 12543,
1380 12548, 12555, 12558, 12560, 12563, 12573, 12576, 12581,
1381 12584, 12585, 12591, 12594, 12609, 12614, 12618, 12621,
1382 12623, 12626, 12630, 12650, 12651, 12653, 12654, 12660,
1383 12669, 12671, 12674, 12678, 12683, 12686, 12695, 12704,
1384 12705, 12711, 12719, 12723, 12726, 12728, 12731, 12734,
1385 12735, 12761, 12768, 12770, 12780, 12788, 12789, 12791,
1386 12794, 12800, 12801, 12804, 12810, 12816, 12819, 12821,
1387 12828, 12833, 12836, 12839, 12846, 12851, 12858, 12866,
1388 12870, 12873, 12879, 12881, 12885, 12896, 12899, 12900,
1389 12909, 12920, 12923, 12924, 12933, 12936, 12944, 12951,
1390 12956, 12959, 12965, 12966, 12969, 12971, 12975, 12984,
1391 12990, 12998, 12999, 13001, 13008, 13010, 13014, 13020,
1392 13026, 13041, 13049, 13053, 13055, 13056, 13059, 13070,
1393 13076, 13080, 13085, 13088, 13091, 13094, 13101, 13104,
1394 13113, 13118, 13124, 13125, 13130, 13131, 13133, 13146,
1395 13148, 13154, 13158, 13160, 13169, 13173, 13178, 13185,
1396 13193, 13196, 13199, 13203, 13208, 13211, 13215, 13218,
1397 13224, 13229, 13239, 13244, 13248, 13250, 13256, 13269,
1398 13278, 13280, 13286, 13295, 13298, 13313, 13316, 13320,
1399 13323, 13334, 13340, 13341, 13343, 13346, 13349, 13350,
1400 13355, 13356, 13358, 13361, 13364, 13365, 13368, 13379,
1401 13388, 13391, 13400, 13406, 13410, 13416, 13419, 13424,
1402 13430, 13431, 13439, 13440, 13445, 13446, 13451, 13460,
1403 13463, 13473, 13475, 13476, 13479, 13490, 13493, 13496,
1404 13505, 13508, 13515, 13521, 13529, 13530, 13533, 13536,
1405 13538, 13545, 13551, 13553, 13554, 13563, 13571, 13589,
1406 13595, 13598, 13605, 13619, 13620, 13626, 13629, 13635,
1407 13638, 13640, 13641, 13649, 13664, 13668, 13680, 13683,
1408 13698, 13703, 13704, 13713, 13715, 13718, 13724, 13728,
1409 13739, 13740, 13743, 13754, 13763, 13764, 13769, 13770,
1410 13775, 13790, 13791, 13805, 13808, 13815, 13823, 13826,
1411 13836, 13844, 13845, 13848, 13850, 13866, 13868, 13869,
1412 13871, 13874, 13875, 13881, 13883, 13886, 13889, 13895,
1413 13896, 13899, 13901, 13904, 13908, 13911, 13913, 13923,
1414 13925, 13941, 13946, 13950, 13958, 13959, 13970, 13971,
1415 13973, 13976, 13980, 13983, 13991, 13998, 14000, 14009,
1416 14013, 14015, 14025, 14028, 14034, 14040, 14043, 14048,
1417 14049, 14054, 14055, 14061, 14075, 14081, 14090, 14091,
1418 14100, 14105, 14109, 14114, 14138, 14139, 14141, 14144,
1419 14148, 14153, 14154, 14159, 14174, 14175, 14193, 14196,
1420 14201, 14204, 14205, 14214, 14216, 14219, 14223, 14231,
1421 14238, 14246, 14249, 14256, 14258, 14268, 14270, 14273,
1422 14274, 14279, 14285, 14286, 14289, 14295, 14298, 14301,
1423 14303, 14309, 14310, 14313, 14315, 14321, 14324, 14328,
1424 14330, 14331, 14334, 14343, 14348, 14351, 14355, 14361,
1425 14364, 14375, 14376, 14379, 14385, 14394, 14396, 14403,
1426 14406, 14408, 14418, 14421, 14429, 14433, 14435, 14439,
1427 14450, 14454, 14460, 14463, 14466, 14474, 14480, 14489,
1428 14504, 14508, 14510, 14511, 14513, 14516, 14529, 14531,
1429 14538, 14550, 14561, 14564, 14565, 14568, 14573, 14576,
1430 14583, 14586, 14589, 14595, 14600, 14603, 14604, 14610,
1431 14615, 14621, 14625, 14634, 14643, 14648, 14651, 14655,
1432 14663, 14666, 14669, 14673, 14681, 14691, 14693, 14694,
1433 14699, 14700, 14705, 14711, 14714, 14718, 14721, 14726,
1434 14736, 14741, 14750, 14763, 14765, 14768, 14783, 14784,
1435 14786, 14790, 14793, 14799, 14805, 14814, 14816, 14820,
1436 14831, 14834, 14835, 14841, 14858, 14861, 14870, 14876,
1437 14879, 14880, 14894, 14901, 14909, 14916, 14918, 14925,
1438 14931, 14933, 14936, 14939, 14940, 14958, 14960, 14963,
1439 14973, 14979, 14991, 14994, 15005, 15006, 15014, 15023,
1440 15029, 15035, 15044, 15045, 15048, 15051, 15054, 15056,
1441 15059, 15066, 15068, 15069, 15080, 15084, 15090, 15093,
1442 15098, 15101, 15105, 15111, 15120, 15126, 15129, 15134,
1443 15135, 15146, 15153, 15156, 15159, 15161, 15170, 15173,
1444 15183, 15194, 15195, 15201, 15213, 15215, 15224, 15233,
1445 15234, 15245, 15246, 15248, 15254, 15258, 15264, 15269,
1446 15276, 15278, 15279, 15288, 15296, 15315, 15318, 15321,
1447 15324, 15330, 15335, 15338, 15344, 15348, 15351, 15353,
1448 15356, 15363, 15378, 15381, 15386, 15390, 15401, 15404,
1449 15408, 15414, 15419, 15420, 15425, 15426, 15429, 15434,
1450 15435, 15440, 15446, 15455, 15465, 15468, 15470, 15474,
1451 15485, 15488, 15491, 15506, 15509, 15516, 15519, 15525,
1452 15531, 15534, 15539, 15540, 15545, 15560, 15561, 15569,
1453 15573, 15575, 15576, 15579, 15588, 15590, 15591, 15594,
1454 15596, 15609, 15611, 15615, 15618, 15623, 15624, 15626,
1455 15629, 15633, 15635, 15638, 15653, 15659, 15660, 15663,
1456 15666, 15668, 15678, 15689, 15693, 15695, 15696, 15698,
1457 15734, 15738, 15740, 15744, 15755, 15756, 15758, 15765,
1458 15770, 15771, 15773, 15783, 15786, 15791, 15800, 15803,
1459 15813, 15821, 15824, 15828, 15831, 15833, 15843, 15849,
1460 15860, 15861, 15863, 15864, 15870, 15875, 15884, 15885,
1461 15896, 15899, 15908, 15923, 15924, 15929, 15936, 15941,
1462 15945, 15953, 15978, 15981, 15986, 15990, 15995, 16001,
1463 16004, 16013, 16014, 16025, 16028, 16029, 16031, 16034,
1464 16038, 16041, 16044, 16049, 16058, 16059, 16070, 16071,
1465 16079, 16086, 16091, 16094, 16095, 16101, 16106, 16116,
1466 16118, 16125, 16128, 16130, 16148, 16149, 16151, 16154,
1467 16160, 16161, 16163, 16170, 16176, 16179, 16181, 16184,
1468 16185, 16188, 16190, 16200, 16205, 16206, 16211, 16214,
1469 16220, 16221, 16233, 16239, 16245, 16248, 16251, 16253,
1470 16265, 16266, 16268, 16280, 16281, 16284, 16286, 16289,
1471 16293, 16301, 16304, 16305, 16310, 16316, 16323, 16326,
1472 16343, 16346, 16353, 16356, 16358, 16359, 16374, 16385,
1473 16389, 16391, 16394, 16398, 16400, 16401, 16415, 16416,
1474 16419, 16421, 16434, 16443, 16454, 16455, 16458, 16466,
1475 16469, 16470, 16478, 16484, 16485, 16491, 16493, 16496,
1476 16499, 16506, 16511, 16514, 16518, 16524, 16526, 16535,
1477 16536, 16541, 16545, 16553, 16556, 16559, 16574, 16575,
1478 16580, 16589, 16590, 16595, 16599, 16601, 16605, 16611,
1479 16623, 16643, 16644, 16650, 16655, 16658, 16664, 16665,
1480 16671, 16673, 16674, 16676, 16679, 16688, 16695, 16701,
1481 16704, 16706, 16713, 16728, 16730, 16734, 16739, 16743,
1482 16746, 16751, 16760, 16764, 16766, 16773, 16781, 16784,
1483 16788, 16790, 16793, 16794, 16799, 16800, 16806, 16808,
1484 16809, 16811, 16814, 16818, 16820, 16823, 16839, 16851,
1485 16856, 16860, 16869, 16874, 16875, 16878, 16883, 16884,
1486 16886, 16895, 16898, 16904, 16905, 16913, 16914, 16925,
1487 16928, 16931, 16935, 16944, 16946, 16955, 16961, 16965,
1488 16968, 16970, 16980, 16983, 16998, 17009, 17015, 17016,
1489 17019, 17028, 17030, 17061, 17063, 17064, 17070, 17073,
1490 17078, 17079, 17085, 17091, 17105, 17106, 17108, 17115,
1491 17126, 17129, 17130, 17133, 17136, 17141, 17148, 17150,
1492 17151, 17156, 17159, 17163, 17168, 17175, 17180, 17183,
1493 17184, 17190, 17201, 17210, 17214, 17219, 17228, 17234,
1494 17235, 17241, 17243, 17249, 17250, 17255, 17256, 17259,
1495 17268, 17271, 17274, 17291, 17294, 17295, 17301, 17303,
1496 17306, 17315, 17324, 17325, 17333, 17336, 17339, 17343,
1497 17346, 17351, 17360, 17364, 17369, 17373, 17378, 17379,
1498 17381, 17390, 17403, 17409, 17420, 17421, 17423, 17424,
1499 17435, 17438, 17441, 17448, 17456, 17459, 17469, 17474,
1500 17480, 17481, 17490, 17511, 17513, 17525, 17526, 17529,
1501 17534, 17540, 17541, 17544, 17549, 17553, 17555, 17558,
1502 17564, 17570, 17574, 17576, 17579, 17585, 17600, 17610,
1503 17613, 17625, 17628, 17633, 17639, 17640, 17645, 17655,
1504 17658, 17661, 17663, 17669, 17676, 17681, 17690, 17696,
1505 17700, 17703, 17709, 17711, 17718, 17723, 17724, 17730,
1506 17745, 17753, 17754, 17760, 17763, 17765, 17766, 17768,
1507 17771, 17784, 17786, 17795, 17796, 17798, 17801, 17808,
1508 17835, 17838, 17864, 17865, 17873, 17876, 17879, 17885,
1509 17898, 17900, 17901, 17904, 17915, 17918, 17919, 17925,
1510 17931, 17934, 17939, 17948, 17949, 17955, 17961, 17966,
1511 17975, 17981, 17984, 17988, 17991, 17996, 17999, 18003,
1512 18005, 18006, 18008, 18018, 18030, 18033, 18036, 18041,
1513 18048, 18053, 18054, 18065, 18068, 18075, 18080, 18093,
1514 18095, 18104, 18108, 18114, 18120, 18125, 18131, 18134,
1515 18138, 18146, 18149, 18153, 18156, 18159, 18170, 18171,
1516 18176, 18186, 18191, 18194, 18216, 18225, 18228, 18233,
1517 18234, 18236, 18239, 18246, 18248, 18261, 18263, 18264,
1518 18270, 18275, 18279, 18281, 18285, 18291, 18293, 18299,
1519 18303, 18314, 18318, 18321, 18326, 18335, 18338, 18341,
1520 18345, 18348, 18354, 18356, 18360, 18369, 18374, 18380,
1521 18383, 18389, 18390, 18393, 18395, 18396, 18404, 18410,
1522 18416, 18423, 18428, 18435, 18438, 18443, 18449, 18450,
1523 18456, 18459, 18461, 18464, 18465, 18471, 18473, 18486,
1524 18489, 18498, 18501, 18506, 18509, 18510, 18519, 18524,
1525 18528, 18530, 18543, 18548, 18558, 18561, 18569, 18579,
1526 18585, 18590, 18594, 18599, 18600, 18608, 18611, 18621,
1527 18626, 18636, 18638, 18653, 18654, 18656, 18660, 18668,
1528 18669, 18678, 18680, 18681, 18684, 18689, 18698, 18704,
1529 18711, 18720, 18723, 18731, 18741, 18744, 18746, 18750,
1530 18753, 18755, 18758, 18764, 18768, 18773, 18774, 18780,
1531 18783, 18785, 18786, 18789, 18794, 18795, 18803, 18809,
1532 18816, 18821, 18824, 18828, 18831, 18845, 18846, 18849,
1533 18858, 18873, 18890, 18891, 18899, 18905, 18906, 18915,
1534 18923, 18926, 18930, 18935, 18939, 18944, 18948, 18953,
1535 18975, 18978, 18981, 18983, 18993, 18995, 18996, 18998,
1536 19005, 19019, 19023, 19026, 19034, 19041, 19056, 19059,
1537 19074, 19076, 19083, 19088, 19091, 19094, 19098, 19100,
1538 19109, 19115, 19118, 19119, 19130, 19136, 19140, 19143,
1539 19149, 19151, 19158, 19160, 19163, 19164, 19166, 19175,
1540 19185, 19188, 19196, 19215, 19223, 19224, 19226, 19229,
1541 19230, 19250, 19271, 19278, 19280, 19283, 19284, 19296,
1542 19301, 19304, 19305, 19314, 19319, 19325, 19326, 19334,
1543 19335, 19338, 19346, 19349, 19353, 19355, 19356, 19361,
1544 19364, 19368, 19373, 19374, 19383, 19391, 19395, 19401,
1545 19410, 19416, 19419, 19425, 19430, 19433, 19436, 19445,
1546 19451, 19458, 19460, 19461, 19466, 19476, 19479, 19485,
1547 19488, 19496, 19509, 19511, 19520, 19521, 19523, 19539,
1548 19544, 19548, 19551, 19553, 19556, 19559, 19566, 19569,
1549 19578, 19580, 19581, 19590, 19595, 19599, 19604, 19608,
1550 19613, 19614, 19616, 19619, 19620, 19625, 19646, 19650,
1551 19656, 19658, 19661, 19670, 19671, 19679, 19683, 19685,
1552 19686, 19691, 19698, 19704, 19709, 19719, 19721, 19725,
1553 19730, 19749, 19751, 19754, 19755, 19760, 19770, 19775,
1554 19781, 19784, 19790, 19803, 19809, 19811, 19815, 19829,
1555 19833, 19835, 19839, 19851, 19854, 19859, 19863, 19866,
1556 19874, 19880, 19884, 19889, 19895, 19899, 19910, 19913,
1557 19914, 19919, 19920, 19923, 19928, 19931, 19934, 19938,
1558 19941, 19943, 19950, 19964, 19968, 19976, 19985, 19989,
1559 19991, 19994, 20004, 20006, 20015, 20018, 20019, 20031,
1560 20043, 20046, 20049, 20055, 20061, 20063, 20064, 20075,
1561 20076, 20081, 20084, 20088, 20094, 20096, 20106, 20115,
1562 20118, 20120, 20126, 20138, 20141, 20144, 20171, 20175,
1563 20178, 20180, 20193, 20211, 20213, 20214, 20216, 20229,
1564 20235, 20241, 20243, 20246, 20249, 20253, 20259, 20264,
1565 20265, 20271, 20279, 20288, 20291, 20295, 20298, 20304,
1566 20313, 20318, 20319, 20346, 20348, 20349, 20354, 20369,
1567 20375, 20379, 20381, 20385, 20393, 20400, 20406, 20409,
1568 20411, 20414, 20420, 20423, 20424, 20426, 20433, 20439,
1569 20441, 20448, 20451, 20463, 20466, 20469, 20474, 20480,
1570 20486, 20496, 20505, 20508, 20511, 20519, 20523, 20525,
1571 20528, 20538, 20540, 20556, 20558, 20565, 20570, 20571,
1572 20574, 20580, 20588, 20589, 20591, 20594, 20600, 20601,
1573 20606, 20610, 20613, 20615, 20616, 20621, 20628, 20631,
1574 20634, 20640, 20649, 20666, 20670, 20675, 20678, 20690,
1575 20693, 20694, 20699, 20705, 20706, 20721, 20726, 20733,
1576 20739, 20745, 20753, 20756, 20759, 20760, 20769, 20771,
1577 20774, 20789, 20796, 20798, 20801, 20804, 20805, 20808,
1578 20810, 20813, 20820, 20823, 20825, 20829, 20834, 20840,
1579 20843, 20859, 20864, 20868, 20879, 20880, 20885, 20888,
1580 20900, 20904, 20906, 20921, 20924, 20925, 20931, 20939,
1581 20943, 20946, 20948, 20951, 20955, 20963, 20970, 20973,
1582 20976, 20978, 20979, 20984, 20990, 20991, 20999, 21006,
1583 21008, 21009, 21011, 21021, 21030, 21035, 21036, 21041,
1584 21044, 21050, 21065, 21069, 21078, 21084, 21089, 21090,
1585 21093, 21096, 21098, 21104, 21110, 21111, 21113, 21119,
1586 21128, 21140, 21141, 21146, 21149, 21153, 21161, 21165,
1587 21168, 21174, 21179, 21186, 21189, 21195, 21198, 21201,
1588 21203, 21204, 21216, 21218, 21221, 21225, 21228, 21230,
1589 21231, 21233, 21236, 21243, 21245, 21249, 21254, 21266,
1590 21278, 21284, 21285, 21288, 21294, 21305, 21320, 21321,
1591 21324, 21333, 21338, 21341, 21344, 21348, 21350, 21351,
1592 21354, 21359, 21363, 21368, 21371, 21375, 21383, 21386,
1593 21393, 21396, 21398, 21410, 21414, 21419, 21420, 21426,
1594 21429, 21431, 21449, 21450, 21461, 21464, 21468, 21471,
1595 21476, 21480, 21483, 21489, 21494, 21501, 21506, 21509,
1596 21518, 21524, 21525, 21531, 21533, 21546, 21551, 21558,
1597 21566, 21575, 21579, 21588, 21594, 21600, 21603, 21611,
1598 21618, 21630, 21635, 21641, 21645, 21656, 21659, 21660,
1599 21665, 21695, 21698, 21699, 21701, 21705, 21713, 21720,
1600 21725, 21728, 21740, 21743, 21749, 21758, 21770, 21771,
1601 21786, 21788, 21789, 21795, 21798, 21803, 21804, 21806,
1602 21813, 21816, 21824, 21825, 21830, 21834, 21845, 21855,
1603 21858, 21860, 21876, 21879, 21888, 21890, 21891, 21893,
1604 21894, 21896, 21900, 21926, 21933, 21944, 21945, 21956,
1605 21966, 21971, 21975, 21980, 21981, 21984, 21986, 21993,
1606 21995, 21998, 22008, 22010, 22013, 22014, 22020, 22026,
1607 22029, 22035, 22043, 22044, 22050, 22055, 22059, 22061,
1608 22064, 22065, 22079, 22085, 22089, 22094, 22100, 22101,
1609 22103, 22110, 22124, 22128, 22131, 22133, 22134, 22136,
1610 22139, 22140, 22146, 22175, 22178, 22185, 22190, 22191,
1611 22194, 22208, 22224, 22226, 22241, 22245, 22248, 22250,
1612 22253, 22259, 22265, 22266, 22268, 22271, 22274, 22281,
1613 22289, 22293, 22308, 22310, 22311, 22316, 22320, 22323,
1614 22325, 22328, 22341, 22343, 22349, 22350, 22355, 22364,
1615 22370, 22376, 22385, 22386, 22388, 22394, 22398, 22404,
1616 22409, 22419, 22421, 22425, 22433, 22439, 22443, 22446,
1617 22454, 22458, 22463, 22469, 22476, 22479, 22481, 22485,
1618 22491, 22493, 22503, 22506, 22526, 22530, 22538, 22541,
1619 22559, 22560, 22563, 22565, 22568, 22569, 22580, 22589,
1620 22590, 22595, 22598, 22616, 22623, 22629, 22631, 22640,
1621 22644, 22646, 22653, 22658, 22659, 22664, 22668, 22670,
1622 22671, 22680, 22688, 22694, 22701, 22706, 22713, 22716,
1623 22719, 22740, 22745, 22748, 22751, 22761, 22766, 22770,
1624 22776, 22778, 22784, 22793, 22794, 22799, 22806, 22815,
1625 22820, 22829, 22833, 22836, 22838, 22845, 22848, 22853,
1626 22868, 22875, 22878, 22881, 22883, 22889, 22908, 22910,
1627 22911, 22913, 22916, 22920, 22926, 22931, 22934, 22943,
1628 22946, 22971, 22974, 22976, 22979, 22985, 22989, 22994,
1629 23010, 23013, 23024, 23025, 23030, 23036, 23045, 23046,
1630 23049, 23051, 23066, 23070, 23073, 23076, 23085, 23090,
1631 23091, 23093, 23099, 23109, 23114, 23118, 23130, 23135,
1632 23136, 23139, 23150, 23153, 23154, 23163, 23168, 23174,
1633 23175, 23190, 23199, 23205, 23219, 23220, 23223, 23225,
1634 23228, 23235, 23238, 23244, 23249, 23253, 23255, 23261,
1635 23274, 23279, 23283, 23286, 23294, 23295, 23300, 23309,
1636 23316, 23319, 23321, 23324, 23331, 23339, 23340, 23343,
1637 23345, 23351, 23361, 23363, 23373, 23375, 23378, 23384,
1638 23385, 23403, 23405, 23408, 23409, 23414, 23415, 23426,
1639 23430, 23433, 23438, 23444, 23450, 23459, 23466, 23478,
1640 23496, 23498, 23508, 23520, 23525, 23528, 23529, 23543,
1641 23546, 23555, 23559, 23561, 23564, 23568, 23571, 23573,
1642 23574, 23580, 23594, 23603, 23610, 23618, 23625, 23634,
1643 23639, 23643, 23646, 23648, 23651, 23654, 23658, 23669,
1644 23675, 23676, 23681, 23690, 23693, 23694, 23703, 23708,
1645 23709, 23715, 23720, 23729, 23745, 23748, 23750, 23753,
1646 23756, 23760, 23763, 23766, 23771, 23781, 23784, 23790,
1647 23795, 23799, 23804, 23811, 23814, 23819, 23826, 23828,
1648 23829, 23840, 23849, 23850, 23855, 23856, 23858, 23868,
1649 23870, 23871, 23888, 23889, 23895, 23898, 23903, 23904,
1650 23909, 23918, 23921, 23928, 23934, 23940, 23951, 23955,
1651 23958, 23966, 23969, 23973, 23975, 23981, 23984, 23988,
1652 23990, 24008, 24011, 24014, 24024, 24036, 24039, 24045,
1653 24054, 24059, 24060, 24065, 24078, 24081, 24089, 24093,
1654 24096, 24098, 24110, 24119, 24123, 24129, 24135, 24140,
1655 24149, 24155, 24156, 24168, 24170, 24176, 24185, 24191,
1656 24198, 24203, 24204, 24206, 24218, 24224, 24231, 24236,
1657 24239, 24240, 24243, 24245, 24248, 24261, 24263, 24266,
1658 24269, 24270, 24281, 24285, 24294, 24296, 24305, 24309,
1659 24311, 24323, 24324, 24330, 24336, 24338, 24339, 24365,
1660 24366, 24375, 24378, 24380, 24383, 24389, 24390, 24393,
1661 24399, 24404, 24408, 24410, 24411, 24423, 24428, 24429,
1662 24434, 24435, 24441, 24444, 24453, 24473, 24476, 24486,
1663 24494, 24495, 24501, 24504, 24509, 24515, 24516, 24518,
1664 24521, 24528, 24534, 24540, 24551, 24554, 24558, 24560,
1665 24561, 24569, 24578, 24584, 24585, 24588, 24596, 24599,
1666 24600, 24603, 24605, 24611, 24626, 24630, 24638, 24639,
1667 24648, 24653, 24665, 24666, 24669, 24681, 24683, 24684,
1668 24695, 24696, 24704, 24705, 24708, 24714, 24716, 24725,
1669 24729, 24731, 24738, 24740, 24749, 24761, 24764, 24765,
1670 24768, 24773, 24774, 24779, 24798, 24801, 24806, 24813,
1671 24816, 24819, 24831, 24833, 24834, 24840, 24848, 24855,
1672 24863, 24869, 24870, 24873, 24878, 24891, 24893, 24894,
1673 24900, 24903, 24905, 24911, 24915, 24921, 24926, 24935,
1674 24938, 24945, 24959, 24960, 24963, 24968, 24969, 24971,
1675 24978, 24995, 24996, 24999, 25010, 25011, 25016, 25023,
1676 25025, 25026, 25034, 25038, 25043, 25046, 25050, 25055,
1677 25059, 25061, 25064, 25065, 25073, 25076, 25079, 25088,
1678 25103, 25110, 25113, 25115, 25130, 25131, 25136, 25143,
1679 25145, 25155, 25160, 25164, 25166, 25170, 25179, 25181,
1680 25188, 25191, 25193, 25205, 25208, 25211, 25220, 25229,
1681 25230, 25248, 25251, 25256, 25263, 25269, 25271, 25274,
1682 25275, 25290, 25293, 25295, 25296, 25299, 25313, 25323,
1683 25325, 25335, 25341, 25353, 25361, 25370, 25376, 25383,
1684 25386, 25388, 25394, 25410, 25416, 25419, 25424, 25428,
1685 25433, 25436, 25445, 25446, 25454, 25461, 25464, 25475,
1686 25478, 25484, 25485, 25494, 25496, 25500, 25515, 25521,
1687 25523, 25529, 25530, 25535, 25554, 25565, 25566, 25568,
1688 25575, 25578, 25584, 25596, 25598, 25599, 25601, 25608,
1689 25614, 25619, 25620, 25628, 25631, 25641, 25643, 25653,
1690 25664, 25670, 25671, 25673, 25674, 25680, 25691, 25703,
1691 25706, 25709, 25710, 25713, 25715, 25718, 25719, 25724,
1692 25730, 25736, 25739, 25740, 25743, 25751, 25755, 25758,
1693 25760, 25769, 25775, 25781, 25788, 25790, 25796, 25799,
1694 25803, 25806, 25815, 25818, 25823, 25829, 25836, 25839,
1695 25841, 25845, 25856, 25859, 25860, 25874, 25883, 25884,
1696 25893, 25898, 25901, 25908, 25913, 25914, 25919, 25926,
1697 25929, 25934, 25935, 25946, 25949, 25953, 25956, 25964,
1698 25970, 25974, 25985, 25986, 25988, 25995, 26004, 26010,
1699 26013, 26025, 26028, 26033, 26034, 26040, 26051, 26060,
1700 26063, 26073, 26076, 26081, 26088, 26090, 26091, 26094,
1701 26100, 26111, 26118, 26124, 26126, 26129, 26133, 26144,
1702 26145, 26150, 26156, 26160, 26180, 26181, 26184, 26189,
1703 26193, 26195, 26216, 26226, 26228, 26244, 26250, 26255,
1704 26258, 26264, 26270, 26271, 26276, 26280, 26283, 26285,
1705 26289, 26291, 26304, 26313, 26315, 26319, 26333, 26336,
1706 26345, 26348, 26354, 26355, 26360, 26363, 26366, 26373,
1707 26378, 26384, 26391, 26403, 26406, 26408, 26418, 26429,
1708 26430, 26439, 26441, 26444, 26450, 26451, 26459, 26468,
1709 26475, 26478, 26481, 26483, 26486, 26490, 26499, 26501,
1710 26508, 26523, 26525, 26534, 26538, 26543, 26544, 26546,
1711 26550, 26556, 26558, 26564, 26573, 26574, 26580, 26585,
1712 26586, 26594, 26598, 26600, 26615, 26616, 26619, 26633,
1713 26634, 26639, 26640, 26649, 26654, 26661, 26663, 26676,
1714 26679, 26688, 26690, 26700, 26703, 26705, 26709, 26718,
1715 26720, 26726, 26739, 26751, 26753, 26763, 26774, 26775,
1716 26784, 26795, 26796, 26798, 26804, 26805, 26808, 26811,
1717 26814, 26816, 26819, 26826, 26828, 26840, 26846, 26849,
1718 26858, 26859, 26865, 26879, 26886, 26888, 26891, 26895,
1719 26906, 26909, 26915, 26924, 26928, 26930, 26940, 26943,
1720 26945, 26948, 26949, 26958, 26961, 26963, 26969, 26975,
1721 26979, 26993, 26996, 27000, 27005, 27006, 27018, 27024,
1722 27029, 27041, 27045, 27050, 27060, 27066, 27069, 27075,
1723 27081, 27083, 27090, 27096, 27108, 27125, 27134, 27138,
1724 27143, 27146, 27155, 27159, 27161, 27165, 27173, 27180,
1725 27183, 27185, 27188, 27200, 27201, 27204, 27206, 27209,
1726 27210, 27218, 27221, 27224, 27234, 27246, 27248, 27249,
1727 27251, 27258, 27260, 27269, 27270, 27273, 27279, 27281,
1728 27288, 27290, 27291, 27300, 27308, 27311, 27314, 27315,
1729 27323, 27333, 27336, 27339, 27354, 27356, 27360, 27363,
1730 27375, 27383, 27386, 27389, 27393, 27399, 27414, 27416,
1731 27425, 27434, 27438, 27440, 27453, 27458, 27459, 27470,
1732 27474, 27479, 27486, 27489, 27491, 27500, 27504, 27510,
1733 27524, 27525, 27528, 27530, 27536, 27539, 27551, 27554,
1734 27558, 27563, 27573, 27581, 27585, 27600, 27603, 27606,
1735 27608, 27609, 27614, 27621, 27624, 27629, 27645, 27656,
1736 27665, 27666, 27668, 27669, 27671, 27675, 27686, 27690,
1737 27699, 27705, 27719, 27720, 27728, 27734, 27743, 27750,
1738 27755, 27764, 27770, 27773, 27789, 27794, 27801, 27804,
1739 27809, 27810, 27815, 27816, 27819, 27830, 27831, 27833,
1740 27836, 27840, 27845, 27848, 27855, 27858, 27860, 27866,
1741 27881, 27893, 27896, 27899, 27903, 27906, 27908, 27909,
1742 27911, 27914, 27918, 27921, 27924, 27935, 27944, 27948,
1743 27950, 27951, 27960, 27963, 27965, 27966, 27974, 27983,
1744 27993, 27998, 28001, 28004, 28019, 28020, 28026, 28040,
1745 28043, 28046, 28049, 28050, 28056, 28061, 28065, 28074,
1746 28083, 28085, 28089, 28098, 28103, 28104, 28118, 28119,
1747 28124, 28131, 28133, 28134, 28149, 28155, 28166, 28179,
1748 28184, 28188, 28191, 28196, 28200, 28208, 28215, 28218,
1749 28221, 28226, 28233, 28236, 28238, 28239, 28244, 28250,
1750 28251, 28254, 28259, 28263, 28265, 28266, 28271, 28284,
1751 28295, 28298, 28299, 28305, 28314, 28316, 28329, 28331,
1752 28335, 28340, 28343, 28350, 28355, 28356, 28365, 28368,
1753 28373, 28383, 28386, 28389, 28391, 28403, 28404, 28406,
1754 28410, 28413, 28421, 28428, 28436, 28445, 28446, 28448,
1755 28454, 28455, 28460, 28461, 28464, 28470, 28475, 28478,
1756 28481, 28491, 28494, 28496, 28499, 28518, 28520, 28523,
1757 28529, 28536, 28538, 28544, 28548, 28553, 28559, 28565,
1758 28569, 28571, 28574, 28581, 28586, 28589, 28595, 28596,
1759 28601, 28610, 28611, 28620, 28625, 28629, 28634, 28635,
1760 28641, 28643, 28650, 28664, 28665, 28673, 28674, 28683,
1761 28686, 28691, 28694, 28698, 28706, 28713, 28728, 28733,
1762 28743, 28746, 28751, 28763, 28764, 28778, 28779, 28785,
1763 28793, 28796, 28800, 28818, 28820, 28824, 28826, 28833,
1764 28839, 28844, 28848, 28854, 28856, 28859, 28863, 28865,
1765 28868, 28875, 28886, 28890, 28893, 28895, 28896, 28901,
1766 28904, 28914, 28919, 28923, 28926, 28929, 28940, 28949,
1767 28950, 28958, 28961, 28971, 28973, 28986, 28988, 28995,
1768 29006, 29013, 29015, 29021, 29024, 29028, 29030, 29033,
1769 29036, 29049, 29054, 29055, 29064, 29073, 29075, 29076,
1770 29084, 29085, 29094, 29096, 29099, 29103, 29105, 29108,
1771 29114, 29115, 29118, 29121, 29135, 29154, 29156, 29160,
1772 29168, 29181, 29183, 29184, 29189, 29195, 29196, 29201,
1773 29205, 29208, 29213, 29219, 29220, 29225, 29226, 29238,
1774 29240, 29255, 29268, 29271, 29274, 29283, 29286, 29289,
1775 29300, 29301, 29306, 29315, 29328, 29330, 29339, 29343,
1776 29346, 29349, 29355, 29363, 29366, 29370, 29378, 29381,
1777 29385, 29393, 29394, 29415, 29444, 29448, 29450, 29453,
1778 29454, 29456, 29460, 29468, 29471, 29481, 29483, 29489,
1779 29495, 29498, 29504, 29505, 29510, 29511, 29514, 29525,
1780 29526, 29531, 29534, 29538, 29541, 29546, 29553, 29556,
1781 29559, 29561, 29570, 29574, 29579, 29583, 29591, 29598,
1782 29603, 29604, 29609, 29610, 29616, 29619, 29621, 29631,
1783 29636, 29640, 29666, 29670, 29675, 29678, 29679, 29684,
1784 29688, 29693, 29696, 29699, 29703, 29708, 29709, 29720,
1785 29721, 29723, 29726, 29733, 29735, 29736, 29748, 29754,
1786 29756, 29769, 29778, 29780, 29783, 29790, 29805, 29808,
1787 29810, 29813, 29814, 29825, 29829, 29831, 29834, 29835,
1788 29846, 29849, 29853, 29861, 29864, 29871, 29873, 29876,
1789 29885, 29889, 29895, 29898, 29904, 29916, 29931, 29939,
1790 29943, 29960, 29964, 29975, 29978, 29985, 29990, 29999,
1791 30006, 30008, 30014, 30018, 30020, 30038, 30041, 30044,
1792 30045, 30050, 30051, 30053, 30063, 30066, 30069, 30074,
1793 30080, 30083, 30084, 30104, 30108, 30111, 30125, 30128,
1794 30129, 30135, 30144, 30146, 30158, 30165, 30168, 30171,
1795 30176, 30186, 30191, 30198, 30206, 30213, 30221, 30224,
1796 30228, 30246, 30248, 30254, 30260, 30263, 30269, 30294,
1797 30300, 30303, 30305, 30308, 30311, 30315, 30318, 30323,
1798 30324, 30329, 30330, 30339, 30344, 30351, 30359, 30363,
1799 30366, 30368, 30378, 30380, 30381, 30386, 30389, 30396,
1800 30405, 30410, 30429, 30434, 30443, 30444, 30449, 30450,
1801 30456, 30458, 30459, 30461, 30468, 30471, 30476, 30480,
1802 30500, 30503, 30513, 30515, 30521, 30525, 30528, 30545,
1803 30549, 30560, 30564, 30570, 30575, 30576, 30584, 30605,
1804 30611, 30615, 30626, 30630, 30641, 30645, 30648, 30665,
1805 30666, 30669, 30671, 30678, 30681, 30689, 30690, 30701,
1806 30704, 30708, 30720, 30731, 30734, 30735, 30741, 30743,
1807 30746, 30753, 30755, 30759, 30771, 30773, 30776, 30779,
1808 30780, 30791, 30801, 30804, 30806, 30813, 30815, 30818,
1809 30821, 30825, 30828, 30833, 30836, 30840, 30843, 30851,
1810 30858, 30861, 30864, 30875, 30878, 30890, 30906, 30909,
1811 30918, 30921, 30930, 30935, 30939, 30954, 30963, 30966,
1812 30974, 30980, 30983, 30989, 30990, 30993, 30995, 31001,
1813 31005, 31008, 31019, 31023, 31026, 31028, 31035, 31040,
1814 31049, 31059, 31064, 31065, 31068, 31070, 31071, 31085,
1815 31094, 31095, 31100, 31103, 31106, 31109, 31116, 31136,
1816 31148, 31149, 31151, 31155, 31161, 31163, 31173, 31175,
1817 31191, 31200, 31208, 31211, 31229, 31233, 31236, 31238,
1818 31241, 31248, 31250, 31253, 31266, 31269, 31274, 31281,
1819 31290, 31295, 31298, 31301, 31308, 31313, 31316, 31319,
1820 31326, 31329, 31341, 31343, 31350, 31361, 31365, 31371,
1821 31376, 31380, 31386, 31395, 31400, 31409, 31413, 31425,
1822 31430, 31434, 31436, 31448, 31451, 31460, 31463, 31464,
1823 31469, 31484, 31485, 31490, 31491, 31493, 31494, 31514,
1824 31515, 31529, 31533, 31536, 31539, 31548, 31551, 31556,
1825 31563, 31565, 31574, 31589, 31598, 31599, 31605, 31620,
1826 31623, 31638, 31640, 31649, 31655, 31656, 31658, 31665,
1827 31668, 31673, 31676, 31680, 31683, 31688, 31694, 31695,
1828 31698, 31704, 31709, 31710, 31719, 31721, 31731, 31733,
1829 31736, 31743, 31746, 31749, 31760, 31763, 31766, 31770,
1830 31779, 31788, 31793, 31794, 31799, 31800, 31803, 31805,
1831 31808, 31814, 31823, 31824, 31829, 31833, 31835, 31844,
1832 31845, 31848, 31851, 31854, 31859, 31863, 31868, 31871,
1833 31880, 31886, 31890, 31896, 31899, 31901, 31904, 31911,
1834 31919, 31920, 31926, 31928, 31931, 31950, 31953, 31956,
1835 31964, 31974, 31988, 31998, 32003, 32006, 32009, 32016,
1836 32018, 32031, 32033, 32040, 32045, 32054, 32061, 32075,
1837 32076, 32078, 32085, 32093, 32094, 32108, 32111, 32115,
1838 32118, 32135, 32139, 32141, 32150, 32151, 32159, 32163,
1839 32166, 32186, 32190, 32199, 32201, 32216, 32219, 32225,
1840 32226, 32241, 32244, 32249, 32256, 32276, 32283, 32288,
1841 32289, 32295, 32300, 32304, 32306, 32310, 32313, 32316,
1842 32330, 32331, 32333, 32339, 32346, 32354, 32358, 32373,
1843 32381, 32390, 32391, 32396, 32405, 32408, 32424, 32426,
1844 32435, 32438, 32439, 32445, 32450, 32459, 32460, 32463,
1845 32468, 32475, 32484, 32498, 32501, 32505, 32513, 32514,
1846 32516, 32526, 32531, 32535, 32544, 32549, 32550, 32555,
1847 32559, 32561, 32564, 32570, 32573, 32583, 32585, 32586,
1848 32589, 32591, 32601, 32606, 32619, 32628, 32633, 32634,
1849 32643, 32646, 32654, 32661, 32663, 32676, 32678, 32685,
1850 32690, 32696, 32703, 32706, 32709, 32711, 32718, 32723,
1851 32724, 32739, 32748, 32759, 32760, 32768, 32769, 32771,
1852 32775, 32778, 32781, 32789, 32790, 32793, 32799, 32804,
1853 32808, 32814, 32816, 32823, 32825, 32828, 32838, 32843,
1854 32849, 32850, 32853, 32856, 32858, 32859, 32864, 32865,
1855 32880, 32888, 32894, 32904, 32913, 32915, 32918, 32919,
1856 32921, 32925, 32933, 32940, 32949, 32960, 32963, 32964,
1857 32975, 32978, 32981, 32990, 32991, 32996, 33014, 33018,
1858 33020, 33023, 33033, 33035, 33041, 33044, 33051, 33053,
1859 33054, 33068, 33080, 33084, 33086, 33089, 33095, 33110,
1860 33119, 33135, 33146, 33150, 33168, 33171, 33173, 33179,
1861 33180, 33186, 33188, 33191, 33201, 33206, 33215, 33224,
1862 33228, 33231, 33233, 33245, 33249, 33254, 33261, 33264,
1863 33266, 33270, 33276, 33284, 33285, 33293, 33296, 33300,
1864 33308, 33314, 33321, 33326, 33341, 33348, 33350, 33356,
1865 33360, 33366, 33369, 33374, 33375, 33381, 33395, 33398,
1866 33404, 33410, 33420, 33425, 33426, 33431, 33438, 33441,
1867 33444, 33459, 33461, 33465, 33471, 33473, 33474, 33479,
1868 33486, 33488, 33501, 33510, 33516, 33521, 33524, 33528,
1869 33530, 33536, 33539, 33551, 33560, 33564, 33569, 33570,
1870 33576, 33578, 33584, 33590, 33593, 33594, 33605, 33606,
1871 33608, 33609, 33615, 33623, 33630, 33635, 33636, 33644,
1872 33653, 33669, 33671, 33674, 33684, 33695, 33699, 33704,
1873 33705, 33710, 33713, 33714, 33716, 33723, 33726, 33738,
1874 33740, 33744, 33746, 33749, 33755, 33761, 33765, 33768,
1875 33773, 33779, 33783, 33788, 33789, 33794, 33800, 33803,
1876 33809, 33815, 33825, 33839, 33849, 33854, 33861, 33866,
1877 33870, 33875, 33878, 33879, 33881, 33888, 33891, 33894,
1878 33900, 33903, 33909, 33914, 33921, 33926, 33933, 33941,
1879 33945, 33950, 33963, 33965, 33966, 33969, 33971, 33978,
1880 33980, 33983, 33989, 33993, 33996, 34011, 34020, 34026,
1881 34029, 34035, 34043, 34049, 34055, 34056, 34070, 34073,
1882 34080, 34085, 34103, 34104, 34106, 34109, 34113, 34119,
1883 34130, 34139, 34140, 34155, 34164, 34175, 34185, 34194,
1884 34199, 34218, 34221, 34223, 34224, 34236, 34238, 34241,
1885 34244, 34245, 34250, 34253, 34260, 34265, 34269, 34271,
1886 34283, 34290, 34298, 34305, 34316, 34319, 34329, 34334,
1887 34341, 34343, 34349, 34355, 34356, 34364, 34368, 34371,
1888 34374, 34383, 34385, 34388, 34395, 34406, 34409, 34410,
1889 34431, 34439, 34440, 34445, 34448, 34449, 34451, 34454,
1890 34458, 34463, 34473, 34481, 34496, 34500, 34505, 34509,
1891 34514, 34515, 34530, 34533, 34536, 34554, 34559, 34563,
1892 34571, 34574, 34575, 34581, 34595, 34596, 34598, 34601,
1893 34610, 34616, 34619, 34623, 34628, 34629, 34631, 34656,
1894 34658, 34668, 34670, 34685, 34689, 34691, 34694, 34700,
1895 34701, 34713, 34715, 34719, 34728, 34731, 34733, 34736,
1896 34740, 34745, 34746, 34748, 34749, 34769, 34778, 34796,
1897 34811, 34826, 34830, 34838, 34845, 34848, 34854, 34868,
1898 34869, 34880, 34881, 34883, 34889, 34904, 34910, 34913,
1899 34914, 34916, 34923, 34928, 34929, 34938, 34949, 34955,
1900 34964, 34965, 34970, 34979, 34995, 34998, 35000, 35001,
1901 35004, 35009, 35019, 35025, 35030, 35033, 35039, 35049,
1902 35055, 35058, 35060, 35061, 35069, 35070, 35078, 35081,
1903 35088, 35090, 35091, 35099, 35100, 35103, 35111, 35114,
1904 35118, 35120, 35124, 35135, 35144, 35148, 35154, 35156,
1905 35160, 35163, 35175, 35186, 35189, 35190, 35196, 35211,
1906 35214, 35219, 35225, 35228, 35229, 35240, 35243, 35244,
1907 35250, 35253, 35264, 35268, 35274, 35285, 35286, 35291,
1908 35294, 35303, 35309, 35310, 35313, 35319, 35328, 35331,
1909 35333, 35343, 35354, 35358, 35364, 35376, 35384, 35391,
1910 35396, 35411, 35420, 35421, 35424, 35426, 35433, 35438,
1911 35439, 35445, 35450, 35456, 35459, 35460, 35468, 35474,
1912 35475, 35478, 35484, 35489, 35490, 35495, 35498, 35499,
1913 35505, 35511, 35519, 35529, 35534, 35540, 35544, 35559,
1914 35564, 35571, 35573, 35576, 35580, 35583, 35585, 35595,
1915 35604, 35616, 35618, 35624, 35628, 35630, 35631, 35643,
1916 35646, 35658, 35663, 35664, 35666, 35669, 35670, 35673,
1917 35676, 35679, 35681, 35693, 35694, 35699, 35705, 35706,
1918 35709, 35714, 35718, 35721, 35726, 35735, 35736, 35739,
1919 35741, 35751, 35763, 35768, 35774, 35775, 35781, 35784,
1920 35796, 35798, 35816, 35823, 35831, 35835, 35846, 35849,
1921 35853, 35855, 35856, 35859, 35870, 35880, 35888, 35894,
1922 35903, 35904, 35910, 35918, 35921, 35924, 35930, 35933,
1923 35939, 35940, 35943, 35949, 35954, 35958, 35966, 35970,
1924 35973, 35981, 35985, 35991, 35993, 35996, 35999, 36009,
1925 36015, 36021, 36023, 36026, 36036, 36038, 36044, 36045,
1926 36050, 36051, 36054, 36069, 36080, 36083, 36084, 36086,
1927 36105, 36110, 36111, 36113, 36114, 36125, 36126, 36134,
1928 36135, 36138, 36143, 36153, 36156, 36168, 36170, 36176,
1929 36183, 36189, 36191, 36210, 36215, 36230, 36233, 36234,
1930 36240, 36246, 36248, 36251, 36266, 36273, 36275, 36279,
1931 36288, 36306, 36308, 36311, 36321, 36323, 36324, 36330,
1932 36335, 36336, 36339, 36344, 36350, 36353, 36359, 36363,
1933 36366, 36369, 36381, 36383, 36398, 36408, 36411, 36429,
1934 36434, 36435, 36441, 36444, 36446, 36450, 36453, 36455,
1935 36461, 36465, 36468, 36474, 36476, 36479, 36486, 36488,
1936 36498, 36504, 36506, 36509, 36518, 36519, 36521, 36530,
1937 36531, 36539, 36545, 36560, 36563, 36566, 36570, 36590,
1938 36594, 36618, 36621, 36629, 36638, 36645, 36651, 36654,
1939 36663, 36665, 36675, 36680, 36681, 36684, 36689, 36693,
1940 36708, 36710, 36716, 36726, 36729, 36735, 36738, 36741,
1941 36758, 36761, 36764, 36773, 36776, 36780, 36785, 36791,
1942 36794, 36798, 36803, 36804, 36806, 36818, 36821, 36825,
1943 36836, 36839, 36840, 36846, 36849, 36854, 36860, 36863,
1944 36875, 36878, 36885, 36891, 36909, 36911, 36923, 36924,
1945 36929, 36933, 36938, 36941, 36948, 36953, 36969, 36971,
1946 36975, 36980, 36986, 36999, 37008, 37010, 37013, 37023,
1947 37025, 37035, 37038, 37046, 37049, 37050, 37065, 37071,
1948 37074, 37079, 37080, 37083, 37088, 37094, 37098, 37100,
1949 37101, 37104, 37109, 37115, 37128, 37139, 37143, 37146,
1950 37148, 37155, 37158, 37161, 37176, 37178, 37181, 37188,
1951 37190, 37191, 37205, 37206, 37209, 37220, 37224, 37226,
1952 37235, 37244, 37253, 37254, 37260, 37263, 37265, 37275,
1953 37280, 37283, 37286, 37293, 37298, 37304, 37305, 37311,
1954 37326, 37343, 37349, 37353, 37356, 37358, 37359, 37364,
1955 37365, 37373, 37379, 37380, 37385, 37389, 37398, 37410,
1956 37413, 37415, 37421, 37428, 37430, 37434, 37436, 37443,
1957 37445, 37448, 37451, 37461, 37464, 37466, 37470, 37479,
1958 37505, 37506, 37508, 37514, 37518, 37520, 37539, 37541,
1959 37554, 37566, 37574, 37580, 37583, 37584, 37590, 37596,
1960 37604, 37605, 37608, 37611, 37613, 37619, 37626, 37634,
1961 37638, 37644, 37653, 37661, 37664, 37668, 37673, 37676,
1962 37683, 37688, 37694, 37695, 37700, 37701, 37703, 37715,
1963 37718, 37739, 37751, 37755, 37760, 37763, 37766, 37769,
1964 37770, 37776, 37778, 37785, 37788, 37791, 37805, 37808,
1965 37809, 37814, 37820, 37826, 37829, 37839, 37841, 37844,
1966 37851, 37853, 37854, 37860, 37865, 37871, 37883, 37886,
1967 37890, 37893, 37896, 37898, 37910, 37916, 37926, 37934,
1968 37941, 37956, 37965, 37968, 37970, 37983, 37989, 37991,
1969 37994, 37995, 37998, 38000, 38001, 38015, 38019, 38039,
1970 38040, 38045, 38049, 38051, 38061, 38064, 38073, 38078,
1971 38079, 38081, 38103, 38106, 38115, 38121, 38124, 38126,
1972 38129, 38130, 38141, 38144, 38151, 38166, 38171, 38183,
1973 38184, 38189, 38193, 38201, 38210, 38211, 38220, 38231,
1974 38235, 38240, 38243, 38246, 38253, 38255, 38259, 38268,
1975 38270, 38271, 38280, 38289, 38298, 38301, 38303, 38315,
1976 38324, 38325, 38333, 38336, 38339, 38348, 38358, 38366,
1977 38376, 38378, 38385, 38388, 38390, 38400, 38409, 38414,
1978 38415, 38418, 38423, 38435, 38436, 38441, 38453, 38456,
1979 38459, 38471, 38474, 38480, 38481, 38495, 38501, 38508,
1980 38511, 38514, 38520, 38523, 38534, 38540, 38546, 38550,
1981 38568, 38570, 38576, 38583, 38585, 38595, 38600, 38606,
1982 38618, 38619, 38621, 38624, 38630, 38631, 38633, 38634,
1983 38639, 38645, 38658, 38661, 38669, 38673, 38675, 38679,
1984 38684, 38688, 38691, 38708, 38709, 38715, 38723, 38735,
1985 38738, 38739, 38744, 38745, 38754, 38756, 38760, 38763,
1986 38771, 38774, 38775, 38778, 38781, 38784, 38786, 38793,
1987 38795, 38805, 38808, 38810, 38820, 38823, 38829, 38840,
1988 38843, 38844, 38849, 38855, 38856, 38859, 38861, 38865,
1989 38871, 38873, 38880, 38886, 38891, 38898, 38900, 38906,
1990 38919, 38924, 38931, 38933, 38946, 38949, 38964, 38966,
1991 38975, 38984, 38988, 38991, 38999, 39003, 39008, 39015,
1992 39020, 39024, 39029, 39039, 39050, 39060, 39068, 39069,
1993 39078, 39081, 39083, 39086, 39089, 39095, 39096, 39101,
1994 39114, 39116, 39120, 39129, 39138, 39141, 39150, 39153,
1995 39155, 39158, 39170, 39173, 39183, 39200, 39213, 39218,
1996 39219, 39233, 39239, 39243, 39248, 39254, 39255, 39258,
1997 39269, 39270, 39276, 39284, 39285, 39288, 39291, 39296,
1998 39303, 39311, 39321, 39324, 39326, 39345, 39348, 39353,
1999 39356, 39360, 39368, 39389, 39390, 39393, 39395, 39398,
2000 39401, 39404, 39411, 39419, 39426, 39428, 39438, 39443,
2001 39444, 39446, 39450, 39459, 39464, 39470, 39488, 39489,
2002 39494, 39515, 39519, 39521, 39531, 39543, 39551, 39555,
2003 39566, 39569, 39573, 39575, 39576, 39579, 39590, 39593,
2004 39596, 39600, 39614, 39615, 39620, 39629, 39636, 39639,
2005 39641, 39650, 39654, 39659, 39666, 39668, 39674, 39678,
2006 39683, 39689, 39696, 39698, 39699, 39705, 39711, 39713,
2007 39716, 39725, 39740, 39746, 39765, 39768, 39774, 39779,
2008 39780, 39789, 39794, 39800, 39804, 39806, 39810, 39813,
2009 39815, 39816, 39828, 39834, 39843, 39845, 39846, 39848,
2010 39849, 39878, 39884, 39888, 39900, 39905, 39906, 39908,
2011 39911, 39914, 39920, 39921, 39923, 39930, 39933, 39936,
2012 39944, 39950, 39951, 39953, 39969, 39971, 39983, 39986,
2013 39989, 39993, 39998, 39999, 0
2014 };
2015
notest(mpz_ptr p,mpz_ptr q)2016 int notest
2017 (mpz_ptr p, mpz_ptr q)
2018 {
2019 assert((p == q) || (p != q)); // dummy to supress compiler warning
2020 return 1;
2021 }
2022
test7mod8(mpz_ptr p,mpz_ptr q)2023 int test7mod8
2024 (mpz_ptr p, mpz_ptr q)
2025 {
2026 assert((p == q) || (p != q)); // dummy to supress compiler warning
2027 return mpz_congruent_ui_p(p, 7L, 8L);
2028 }
2029
test3mod4(mpz_ptr p,mpz_ptr q)2030 int test3mod4
2031 (mpz_ptr p, mpz_ptr q)
2032 {
2033 assert((p == q) || (p != q)); // dummy to supress compiler warning
2034 return mpz_congruent_ui_p(p, 3L, 4L);
2035 }
2036
2037 /** Miller-Rabin witness test, basically algorithm 4.24 [HAC], for a
2038 fixed base.
2039
2040 @returns 1, if the number @a base is a Miller-Rabin witness to the
2041 compositness of @a n.
2042 @returns 0, otherwise. */
2043
tmcg_mpz_mr_witness(mpz_srcptr n,mpz_srcptr base)2044 int tmcg_mpz_mr_witness
2045 (mpz_srcptr n, mpz_srcptr base)
2046 {
2047 int result = 1;
2048 mpz_t y, r, nm1;
2049
2050 mpz_init(y), mpz_init(nm1), mpz_init(r);
2051
2052 // 1. Write $\mathtt{n} - 1 = 2^s r$ such that $r$ is odd.
2053 mpz_sub_ui(nm1, n, 1L);
2054 unsigned long int s = mpz_scan1(nm1, 0L);
2055 mpz_tdiv_q_2exp(r, nm1, s);
2056 if (mpz_odd_p(r))
2057 {
2058 // 2.2 Compute $y = \mathtt{base}^r \bmod \mathtt{n}$.
2059 mpz_powm(y, base, r, n);
2060 result = 0;
2061
2062 // 2.3 If $y \neq 1$ and $y \neq \mathtt{n} - 1$ then do the following:
2063 if ((mpz_cmp_ui(y, 1L) != 0) && (mpz_cmp(y, nm1) != 0))
2064 {
2065 for (unsigned long int j = 1; j < s; j++)
2066 {
2067 mpz_mul(y, y, y);
2068 mpz_mod(y, y, n);
2069 if (mpz_cmp_ui(y, 1L) == 0)
2070 {
2071 result = 1;
2072 break;
2073 }
2074 if (mpz_cmp(y, nm1) == 0)
2075 break;
2076 }
2077 // strong witness?
2078 if (mpz_cmp(y, nm1) != 0)
2079 result = 1;
2080 }
2081 }
2082
2083 mpz_clear(y), mpz_clear(nm1), mpz_clear(r);
2084 return result;
2085 }
2086
tmcg_mpz_mr_witness_fast(mpz_srcptr n,mpz_srcptr base,mpz_ptr y,mpz_srcptr nm1,mpz_ptr r)2087 bool tmcg_mpz_mr_witness_fast
2088 (mpz_srcptr n, mpz_srcptr base, mpz_ptr y, mpz_srcptr nm1, mpz_ptr r)
2089 {
2090 // 1. Write $\mathtt{n} - 1 = 2^s r$ such that $r$ is odd.
2091 unsigned long int s = mpz_scan1(nm1, 0L);
2092 mpz_tdiv_q_2exp(r, nm1, s);
2093 if (mpz_even_p(r))
2094 return true;
2095
2096 // 2.2 Compute $y = \mathtt{base}^r \bmod \mathtt{n}$.
2097 mpz_powm(y, base, r, n);
2098
2099 // 2.3 If $y \neq 1$ and $y \neq \mathtt{n} - 1$ then do the following:
2100 if ((mpz_cmp_ui(y, 1L) != 0) && (mpz_cmp(y, nm1) != 0))
2101 {
2102 for (unsigned long int j = 1; j < s; j++)
2103 {
2104 mpz_mul(y, y, y);
2105 mpz_mod(y, y, n);
2106 if (mpz_cmp_ui(y, 1L) == 0)
2107 return true;
2108 if (mpz_cmp(y, nm1) == 0)
2109 break;
2110 }
2111 // strong witness?
2112 if (mpz_cmp(y, nm1) != 0)
2113 return true;
2114 }
2115 return false;
2116 }
2117
2118 /** The fast generation of safe primes is implemented according to [CS00]
2119 and M.J. Wiener's "Safe Prime Generation with a Combined Sieve". */
2120
tmcg_mpz_sprime_test(mpz_ptr p,mpz_ptr q,const unsigned long int qsize,int (* test)(mpz_ptr,mpz_ptr),const unsigned long int mr_iterations,const size_t primes_size)2121 void tmcg_mpz_sprime_test
2122 (mpz_ptr p, mpz_ptr q,
2123 const unsigned long int qsize,
2124 int (*test)(mpz_ptr, mpz_ptr),
2125 const unsigned long int mr_iterations,
2126 const size_t primes_size)
2127 {
2128 unsigned long int R_q[SIEVE_SIZE], R_p[SIEVE_SIZE];
2129 mpz_t tmp, y, pm1, qm1, a;
2130
2131 mpz_init(tmp), mpz_init(y), mpz_init(pm1), mpz_init(qm1);
2132 mpz_init_set_ui(a, 2L);
2133
2134 /* Step 1. [CS00]: choose randomly an odd number $q$ of appropriate size */
2135 do
2136 tmcg_mpz_srandomb(q, qsize);
2137 while (mpz_sizeinbase(q, 2L) < qsize);
2138 if (mpz_even_p(q))
2139 mpz_add_ui(q, q, 1L);
2140
2141 /* Compute $p = 2q + 1$. */
2142 mpz_mul_2exp(pm1, q, 1L), mpz_add_ui(p, pm1, 1L);
2143 mpz_sub_ui(qm1, q, 1L);
2144
2145 /* Initalize the sieves for testing divisability by small primes. */
2146 for (size_t i = 0; i < SIEVE_SIZE; i++)
2147 {
2148 mpz_set_ui(tmp, primes[i]);
2149 /* R_q[i] = q mod primes[i] */
2150 mpz_mod(y, q, tmp);
2151 R_q[i] = mpz_get_ui(y);
2152 /* R_p[i] = (2q+1) mod primes[i] */
2153 mpz_mod(y, p, tmp);
2154 R_p[i] = mpz_get_ui(y);
2155 }
2156
2157 while (1)
2158 {
2159 /* Increase $q$ by 2 (incremental prime number generator). */
2160 mpz_add_ui(q, q, 2L), mpz_add_ui(qm1, qm1, 2L);
2161
2162 /* Increase $p$ by 4 (actually compute $p = 2q + 1$). */
2163 mpz_add_ui(p, p, 4L), mpz_add_ui(pm1, pm1, 4L);
2164
2165 /* Use the sieve optimization procedure of Note 4.51(ii) [HAC]. */
2166 bool fail = false;
2167 for (size_t i = 0; i < SIEVE_SIZE; i++)
2168 {
2169 /* Update the sieves. */
2170 R_q[i] += 2, R_q[i] %= primes[i], R_p[i] += 4, R_p[i] %= primes[i];
2171 /* Check whether R_q[i] or R_p[i] is zero. We cannot break this
2172 loop, because we have to update the sieves completely for the
2173 next round. */
2174 if ((R_q[i] == 0) || (R_p[i] == 0))
2175 fail = true;
2176 }
2177 if (fail)
2178 continue;
2179
2180 /* Additional tests? */
2181 if (!test(p, q))
2182 continue;
2183
2184 /* Step 2. [CS00]: M.J. Wiener's "Combined Sieve"
2185 Check whether $q$ or $p$ are divisable by any primes up to $B$. */
2186 for (size_t i = 0; i < primes_size; i++)
2187 {
2188 if (mpz_congruent_ui_p(q, primes_m1d2[i], primes[i]) ||
2189 mpz_congruent_ui_p(p, primes_m1d2[i], primes[i]))
2190 {
2191 fail = true;
2192 break;
2193 }
2194 if (i >= SIEVE_SIZE)
2195 {
2196 if (mpz_congruent_ui_p(q, 0L, primes[i]) ||
2197 mpz_congruent_ui_p(p, 0L, primes[i]))
2198 {
2199 fail = true;
2200 break;
2201 }
2202 }
2203 }
2204 if (fail)
2205 continue;
2206
2207 /* Step 3. [CS00]: Test whether 2 is not a Miller-Rabin witness to the
2208 compositeness of $q$. */
2209 if (tmcg_mpz_mr_witness_fast(q, a, y, qm1, tmp))
2210 continue;
2211
2212 /* Step 4. [CS00]: Test whether $2^q \equiv \pm 1 \pmod{p}$. */
2213 mpz_powm(y, a, q, p);
2214 if ((mpz_cmp_ui(y, 1L) != 0) && (mpz_cmp(y, pm1) != 0))
2215 continue;
2216
2217 /* Step 5. [CS00]: Apply the Miller-Rabin test to $q$ a defined number
2218 of times (maximum error probability $4^{-mr_iterations}$) using
2219 randomly selected bases. */
2220 if (mpz_probab_prime_p(q, mr_iterations - 1))
2221 break;
2222 }
2223 mpz_clear(tmp), mpz_clear(y), mpz_clear(pm1), mpz_clear(qm1), mpz_clear(a);
2224 }
2225
2226 // A naive generator for safe primes
2227
tmcg_mpz_sprime_test_naive(mpz_ptr p,mpz_ptr q,const unsigned long int qsize,int (* test)(mpz_ptr,mpz_ptr),const unsigned long int mr_iterations,const size_t primes_size)2228 void tmcg_mpz_sprime_test_naive
2229 (mpz_ptr p, mpz_ptr q,
2230 const unsigned long int qsize,
2231 int (*test)(mpz_ptr, mpz_ptr),
2232 const unsigned long int mr_iterations,
2233 const size_t primes_size)
2234 {
2235 /* Choose randomly an odd number $q$ of appropriate size. */
2236 do
2237 tmcg_mpz_srandomb(q, qsize);
2238 while (mpz_sizeinbase(q, 2L) < qsize);
2239 if (mpz_even_p(q))
2240 mpz_add_ui(q, q, 1L);
2241
2242 while (1)
2243 {
2244 /* Increase $q$ by 2 (incremental prime number generator). */
2245 mpz_add_ui(q, q, 2L);
2246 /* Compute $p = 2q + 1$. */
2247 mpz_mul_2exp(p, q, 1L);
2248 mpz_add_ui(p, p, 1L);
2249
2250 /* Additional tests? */
2251 if (!test(p, q))
2252 continue;
2253
2254 /* Check whether $q$ or $p$ are divisable by any primes up to $B$. */
2255 bool fail = false;
2256 for (size_t i = 0; i < primes_size; i++)
2257 {
2258 if (mpz_congruent_ui_p(q, primes_m1d2[i], primes[i]) ||
2259 mpz_congruent_ui_p(p, primes_m1d2[i], primes[i]) ||
2260 mpz_congruent_ui_p(q, 0L, primes[i]) ||
2261 mpz_congruent_ui_p(p, 0L, primes[i]))
2262 {
2263 fail = true;
2264 break;
2265 }
2266 }
2267 if (fail)
2268 continue;
2269
2270 if (!mpz_probab_prime_p(p, 1))
2271 continue;
2272
2273 if (!mpz_probab_prime_p(q, mr_iterations))
2274 continue;
2275
2276 if (mpz_probab_prime_p(p, mr_iterations - 1))
2277 break;
2278 }
2279 }
2280
2281 // A non-incremental generator for safe primes (slow for $\log_2 p \ge 1024$)
2282
tmcg_mpz_sprime_test_noninc(mpz_ptr p,mpz_ptr q,const unsigned long int qsize,int (* test)(mpz_ptr,mpz_ptr),const unsigned long int mr_iterations,const size_t primes_size)2283 void tmcg_mpz_sprime_test_noninc
2284 (mpz_ptr p, mpz_ptr q,
2285 const unsigned long int qsize,
2286 int (*test)(mpz_ptr, mpz_ptr),
2287 const unsigned long int mr_iterations,
2288 const size_t primes_size)
2289 {
2290 while (1)
2291 {
2292 /* Choose randomly an odd number $q$ of appropriate size. */
2293 do
2294 tmcg_mpz_srandomb(q, qsize);
2295 while (mpz_sizeinbase(q, 2L) < qsize);
2296 if (mpz_even_p(q))
2297 mpz_add_ui(q, q, 1L);
2298
2299 /* Compute $p = 2q + 1$. */
2300 mpz_mul_2exp(p, q, 1L);
2301 mpz_add_ui(p, p, 1L);
2302
2303 /* Additional tests? */
2304 if (!test(p, q))
2305 continue;
2306
2307 /* Check whether $q$ or $p$ are divisable by any primes up to $B$. */
2308 bool fail = false;
2309 for (size_t i = 0; i < primes_size; i++)
2310 {
2311 if (mpz_congruent_ui_p(q, primes_m1d2[i], primes[i]) ||
2312 mpz_congruent_ui_p(p, primes_m1d2[i], primes[i]) ||
2313 mpz_congruent_ui_p(q, 0L, primes[i]) ||
2314 mpz_congruent_ui_p(p, 0L, primes[i]))
2315 {
2316 fail = true;
2317 break;
2318 }
2319 }
2320 if (fail)
2321 continue;
2322
2323 // Check that $p$ and $q$ are probable prime.
2324 if (!mpz_probab_prime_p(p, 1))
2325 continue;
2326 if (!mpz_probab_prime_p(q, mr_iterations))
2327 continue;
2328 if (mpz_probab_prime_p(p, mr_iterations - 1))
2329 break;
2330 }
2331 }
2332
tmcg_mpz_sprime(mpz_ptr p,mpz_ptr q,const unsigned long int qsize,const unsigned long int mr_iterations)2333 void tmcg_mpz_sprime
2334 (mpz_ptr p, mpz_ptr q,
2335 const unsigned long int qsize,
2336 const unsigned long int mr_iterations)
2337 {
2338 tmcg_mpz_sprime_test(p, q, qsize, notest, mr_iterations, PRIMES);
2339 }
2340
tmcg_mpz_smprime(mpz_ptr p,mpz_ptr q,const unsigned long int qsize,const unsigned long int mr_iterations)2341 void tmcg_mpz_smprime
2342 (mpz_ptr p, mpz_ptr q,
2343 const unsigned long int qsize,
2344 const unsigned long int mr_iterations)
2345 {
2346 tmcg_mpz_sprime_test(p, q, qsize, notest, mr_iterations, MPRIMES);
2347 }
2348
tmcg_mpz_sprime_naive(mpz_ptr p,mpz_ptr q,const unsigned long int qsize,const unsigned long int mr_iterations)2349 void tmcg_mpz_sprime_naive
2350 (mpz_ptr p, mpz_ptr q,
2351 const unsigned long int qsize,
2352 const unsigned long int mr_iterations)
2353 {
2354 tmcg_mpz_sprime_test_naive(p, q, qsize, notest, mr_iterations, PRIMES);
2355 }
2356
tmcg_mpz_sprime_noninc(mpz_ptr p,mpz_ptr q,const unsigned long int qsize,const unsigned long int mr_iterations)2357 void tmcg_mpz_sprime_noninc
2358 (mpz_ptr p, mpz_ptr q,
2359 const unsigned long int qsize,
2360 const unsigned long int mr_iterations)
2361 {
2362 tmcg_mpz_sprime_test_noninc(p, q, qsize, notest, mr_iterations, PRIMES);
2363 }
2364
tmcg_mpz_sprime2g(mpz_ptr p,mpz_ptr q,const unsigned long int qsize,const unsigned long int mr_iterations)2365 void tmcg_mpz_sprime2g
2366 (mpz_ptr p, mpz_ptr q,
2367 const unsigned long int qsize,
2368 const unsigned long int mr_iterations)
2369 {
2370 /* The additional test is required, if we want 2 as generator of
2371 $\mathbb{QR}_p$. If $p$ is congruent 7 modulo 8, then 2 is a
2372 quadratic residue and hence it will generate the cyclic subgroup
2373 of prime order $q = (p-1)/2$. [RS00] */
2374 tmcg_mpz_sprime_test(p, q, qsize, test7mod8, mr_iterations, PRIMES);
2375 }
2376
tmcg_mpz_sprime3mod4(mpz_ptr p,const unsigned long int psize,const unsigned long int mr_iterations)2377 void tmcg_mpz_sprime3mod4
2378 (mpz_ptr p,
2379 const unsigned long int psize,
2380 const unsigned long int mr_iterations)
2381 {
2382 mpz_t q;
2383
2384 /* This test is required, if we want to construct a Blum integer $n$,
2385 i.e. a number where both factors are primes congruent 3 modulo 4. */
2386 mpz_init(q);
2387 tmcg_mpz_sprime_test(p, q, psize - 1L, test3mod4, mr_iterations, PRIMES);
2388 mpz_clear(q);
2389 }
2390
tmcg_mpz_lprime(mpz_ptr p,mpz_ptr q,mpz_ptr k,const unsigned long int psize,const unsigned long int qsize,const unsigned long int mr_iterations)2391 void tmcg_mpz_lprime
2392 (mpz_ptr p, mpz_ptr q, mpz_ptr k,
2393 const unsigned long int psize,
2394 const unsigned long int qsize,
2395 const unsigned long int mr_iterations)
2396 {
2397 mpz_t foo;
2398 if (qsize >= psize)
2399 throw std::invalid_argument("tmcg_mpz_lprime: qsize >= psize");
2400
2401 /* Choose randomly a prime number $q$ of appropriate size.
2402 Primes of this type are only for public usage, because
2403 we use weak random numbers here! */
2404 do
2405 tmcg_mpz_wrandomb(q, qsize);
2406 while ((mpz_sizeinbase(q, 2L) < qsize) ||
2407 !mpz_probab_prime_p(q, mr_iterations));
2408
2409 mpz_init(foo);
2410 do
2411 {
2412 /* Choose randomly an even number $k$ and compute $p:= qk + 1$. */
2413 do
2414 tmcg_mpz_wrandomb(k, psize - qsize);
2415 while (mpz_sizeinbase(k, 2L) < (psize - qsize));
2416 if (mpz_odd_p(k))
2417 mpz_add_ui(k, k, 1L);
2418 mpz_mul(p, q, k);
2419 mpz_add_ui(p, p, 1L);
2420 /* Check wether $k$ and $q$ are coprime, i.e. $gcd(k, q) = 1$. */
2421 mpz_gcd(foo, k, q);
2422 }
2423 while (mpz_cmp_ui(foo, 1L) || (mpz_sizeinbase(p, 2L) < psize) ||
2424 !mpz_probab_prime_p(p, mr_iterations));
2425 mpz_clear(foo);
2426 }
2427
tmcg_mpz_lprime_prefix(mpz_ptr p,mpz_ptr q,mpz_ptr k,const unsigned long int psize,const unsigned long int qsize,const unsigned long int mr_iterations)2428 void tmcg_mpz_lprime_prefix
2429 (mpz_ptr p, mpz_ptr q, mpz_ptr k,
2430 const unsigned long int psize,
2431 const unsigned long int qsize,
2432 const unsigned long int mr_iterations)
2433 {
2434 mpz_t foo;
2435 if (qsize >= psize)
2436 throw std::invalid_argument("tmcg_mpz_lprime_prefix: qsize >= psize");
2437
2438 mpz_init(foo);
2439 do
2440 {
2441 /* Choose randomly a prime number $q$ of appropriate size.
2442 Primes of this type are only for public usage, because
2443 we use weak random numbers here! */
2444 do
2445 tmcg_mpz_wrandomb(q, qsize);
2446 while ((mpz_sizeinbase(q, 2L) < qsize) ||
2447 !mpz_probab_prime_p(q, mr_iterations));
2448 /* Enhance given $k$ by multiples of TMCG_MPZ_IO_BASE. */
2449 while (mpz_sizeinbase(k, 2L) < (psize - qsize))
2450 mpz_mul_ui(k, k, TMCG_MPZ_IO_BASE);
2451 if (mpz_odd_p(k))
2452 mpz_add_ui(k, k, 1L);
2453 mpz_mul(p, q, k);
2454 mpz_add_ui(p, p, 1L);
2455 /* Check wether $k$ and $q$ are coprime, i.e. $gcd(k, q) = 1$. */
2456 mpz_gcd(foo, k, q);
2457 }
2458 while (mpz_cmp_ui(foo, 1L) || (mpz_sizeinbase(p, 2L) < psize) ||
2459 !mpz_probab_prime_p(p, mr_iterations));
2460 mpz_clear(foo);
2461 }
2462
tmcg_mpz_oprime(mpz_ptr p,const unsigned long int psize,const unsigned long int mr_iterations)2463 void tmcg_mpz_oprime
2464 (mpz_ptr p,
2465 const unsigned long int psize,
2466 const unsigned long int mr_iterations)
2467 {
2468 /* Choose randomly an odd number $p$ of appropriate size. */
2469 do
2470 tmcg_mpz_srandomb(p, psize);
2471 while (mpz_sizeinbase(p, 2L) < psize);
2472 if (mpz_even_p(p))
2473 mpz_add_ui(p, p, 1L);
2474
2475 /* Add two as long as $p$ is not probable prime. */
2476 while (!mpz_probab_prime_p(p, mr_iterations))
2477 mpz_add_ui(p, p, 2L);
2478 }
2479
tmcg_mpz_oprime_noninc(mpz_ptr p,const unsigned long int psize,const unsigned long int mr_iterations)2480 void tmcg_mpz_oprime_noninc
2481 (mpz_ptr p,
2482 const unsigned long int psize,
2483 const unsigned long int mr_iterations)
2484 {
2485 do
2486 {
2487 /* Choose randomly an odd number $p$ of appropriate size. */
2488 do
2489 tmcg_mpz_srandomb(p, psize);
2490 while (mpz_sizeinbase(p, 2L) < psize);
2491 if (mpz_even_p(p))
2492 mpz_add_ui(p, p, 1L);
2493 /* Check whether this number is probably prime. */
2494 }
2495 while (!mpz_probab_prime_p(p, mr_iterations));
2496 }
2497
2498