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