# def pow(b,c,m):
#   if c == 1:
#     return b%m
#   else:
#     return ((b*(pow(b, c-1, m)))%m)
# 
# 
# for j in range(1, 501):
#   L = []
#   for b in range(1, j+1):
#       m = []
#       for i in range(1, j+1):
#         r = pow(b, i, j)
#         while r not in m:
#           m.append(r)
#       if len(m) not in L:
#         L.append(len(m))
#   print j, len(L)

1 1
2 1
3 2
4 2
5 3
6 2
7 4
8 3
9 4
10 3
11 4
12 3
13 6
14 4
15 3
16 3
17 5
18 4
19 6
20 5
21 4
22 4
23 4
24 4
25 6
26 6
27 6
28 6
29 6
30 3
31 8
32 6
33 4
34 5
35 6
36 6
37 9
38 6
39 6
40 6
41 8
42 4
43 8
44 7
45 7
46 4
47 4
48 5
49 8
50 6
51 5
52 9
53 6
54 6
55 6
56 8
57 6
58 6
59 4
60 5
61 12
62 8
63 6
64 7
65 6
66 4
67 8
68 9
69 4
70 6
71 8
72 8
73 12
74 9
75 7
76 10
77 8
78 6
79 8
80 6
81 9
82 8
83 4
84 6
85 5
86 8
87 6
88 10
89 8
90 7
91 6
92 7
93 8
94 4
95 9
96 7
97 12
98 8
99 9
100 10
101 9
102 5
103 8
104 11
105 6
106 6
107 4
108 10
109 12
110 6
111 9
112 9
113 10
114 6
115 6
116 11
117 9
118 4
119 10
120 6
121 8
122 12
123 8
124 13
125 10
126 6
127 12
128 8
129 8
130 6
131 8
132 7
133 6
134 8
135 10
136 12
137 8
138 4
139 8
140 9
141 4
142 8
143 12
144 9
145 6
146 12
147 8
148 15
149 6
150 7
151 12
152 14
153 13
154 8
155 12
156 9
157 12
158 8
159 6
160 7
161 8
162 9
163 10
164 14
165 6
166 4
167 4
168 8
169 12
170 5
171 10
172 13
173 6
174 6
175 13
176 11
177 4
178 8
179 4
180 9
181 18
182 6
183 12
184 10
185 9
186 8
187 10
188 7
189 10
190 9
191 8
192 8
193 14
194 12
195 6
196 13
197 9
198 9
199 12
200 13
201 8
202 9
203 12
204 9
205 8
206 8
207 10
208 11
209 12
210 6
211 16
212 11
213 8
214 4
215 12
216 14
217 8
218 12
219 12
220 10
221 10
222 9
223 8
224 11
225 15
226 10
227 4
228 10
229 12
230 6
231 8
232 15
233 8
234 9
235 6
236 7
237 8
238 10
239 8
240 6
241 20
242 8
243 11
244 19
245 13
246 8
247 9
248 17
249 4
250 10
251 8
252 6
253 8
254 12
255 5
256 8
257 9
258 8
259 9
260 9
261 16
262 8
263 4
264 10
265 6
266 6
267 8
268 14
269 6
270 10
271 16
272 12
273 6
274 8
275 9
276 7
277 12
278 8
279 13
280 11
281 16
282 4
283 8
284 15
285 9
286 12
287 16
288 12
289 10
290 6
291 12
292 20
293 6
294 8
295 6
296 20
297 16
298 6
299 12
300 10
301 8
302 12
303 9
304 14
305 12
306 13
307 12
308 13
309 8
310 12
311 8
312 11
313 16
314 12
315 9
316 14
317 6
318 6
319 12
320 10
321 4
322 8
323 15
324 15
325 14
326 10
327 12
328 18
329 8
330 6
331 16
332 7
333 15
334 4
335 12
336 9
337 20
338 12
339 10
340 9
341 8
342 10
343 12
344 18
345 6
346 6
347 4
348 11
349 12
350 13
351 14
352 15
353 12
354 4
355 12
356 15
357 10
358 4
359 4
360 11
361 12
362 18
363 9
364 9
365 12
366 12
367 8
368 12
369 20
370 9
371 12
372 13
373 12
374 10
375 10
376 10
377 12
378 10
379 16
380 15
381 12
382 8
383 4
384 9
385 12
386 14
387 13
388 21
389 6
390 6
391 10
392 18
393 8
394 9
395 12
396 13
397 18
398 12
399 6
400 14
401 15
402 8
403 12
404 16
405 14
406 12
407 18
408 12
409 16
410 8
411 8
412 14
413 8
414 10
415 6
416 14
417 8
418 12
419 8
420 9
421 24
422 16
423 10
424 15
425 13
426 8
427 12
428 7
429 12
430 12
431 8
432 14
433 20
434 8
435 6
436 21
437 12
438 12
439 8
440 13
441 13
442 10
443 8
444 15
445 8
446 8
447 6
448 13
449 14
450 15
451 8
452 18
453 12
454 4
455 6
456 14
457 16
458 12
459 18
460 11
461 12
462 8
463 16
464 14
465 12
466 8
467 4
468 9
469 8
470 6
471 12
472 10
473 16
474 8
475 20
476 17
477 16
478 8
479 4
480 7
481 9
482 20
483 8
484 14
485 12
486 11
487 12
488 25
489 10
490 13
491 12
492 14
493 10
494 9
495 14
496 21
497 16
498 4
499 8
500 16