0 1
1 2
2 5
3 7
4 9
5 11
6 10
7 15
8 14
9 19
10 21
11 21
12 28
13 24
14 29
15 26
16 26
17 35
18 37
19 39
20 41
21 34
22 43
23 47
24 49
25 56
26 42
27 55
28 57
29 50
30 56
31 50
32 60
33 74
34 69
35 76
36 52
37 70
38 84
39 79
40 81
41 66
42 85
43 74
44 98
45 91
46 74
47 88
48 97
49 99
50 86
51 84
52 105
53 107
54 109
55 122
56 90
57 98
58 124
59 119
60 121
61 105
62 125
63 127
64 112
65 131
66 112
67 135
68 130
69 139
70 132
71 100
72 152
73 140
74 149
75 151
76 122
77 183
78 134
79 159
80 161
81 128
82 165
83 167
84 169
85 146
86 147
87 175
88 194
89 168
90 196
91 146
92 158
93 187
94 189
95 182
96 154
97 195
98 184
99 180
100 201
101 162
102 205
103 224
104 220
105 211
106 148
107 215
108 204
109 228
110 242
111 189
112 225
113 194
114 220
115 216
116 196
117 235
118 237
119 248
120 215
121 208
122 245
123 247
124 238
125 251
126 202
127 216
128 257
129 280
130 250
131 210
132 273
133 267
134 230
135 271
136 231
137 275
138 277
139 279
140 281
141 196
142 308
143 314
144 289
145 291
146 228
147 295
148 254
149 280
150 316
151 242
152 305
153 294
154 338
155 280
156 250
157 315
158 317
159 308
160 321
161 260
162 278
163 327
164 329
165 343
166 256
167 335
168 364
169 301
170 341
171 274
172 345
173 364
174 338
175 351
176 266
177 355
178 357
179 370
180 372
181 308
182 350
183 304
184 348
185 371
186 315
187 410
188 377
189 379
190 326
191 306
192 370
193 387
194 420
195 391
196 320
197 338
198 434
199 399
200 376
201 322
202 392
203 384
204 350
205 411
206 330
207 448
208 417
209 458
210 421
211 294
212 425
213 440
214 429
215 431
216 346
217 408
218 387
219 460
220 532
221 354
222 420
223 430
224 449
225 386
226 362
227 442
228 457
229 459
230 461
231 400
232 398
233 504
234 440
235 471
236 399
237 460
238 490
239 410
240 462
241 372
242 553
243 487
244 489
245 476
246 366
247 495
248 484
249 499
250 501
251 384
252 518
253 468
254 490
255 511
256 410
257 532
258 517
259 560
260 432
261 441
262 525
263 527
264 578
265 556
266 426
267 473
268 504
269 518
270 541
271 434
272 588
273 547
274 470
275 602
276 442
277 555
278 540
279 528
280 546
281 388
282 565
283 567
284 569
285 560
286 521
287 575
288 504
289 579
290 581
291 466
292 585
293 587
294 608
295 506
296 474
297 665
298 588
299 599
300 601
301 482
302 496
303 607
304 609
305 611
306 490
307 632
308 674
309 530
310 621
311 588
312 625
313 627
314 629
315 616
316 430
317 600
318 637
319 640
320 641
321 514
322 660
323 554
324 700
325 666
326 522
327 630
328 657
329 659
330 612
331 532
332 650
333 650
334 700
335 686
336 504
337 616
338 677
339 679
340 681
341 592
342 685
343 687
344 590
345 691
346 554
347 670
348 697
349 699
350 756
351 484
352 770
353 664
354 728
355 672
356 560
357 748
358 614
359 719
360 700
361 609
362 725
363 868
364 729
365 645
366 586
367 735
368 760
369 739
370 696
371 594
372 638
373 747
374 756
375 751
376 644
377 755
378 730
379 650
380 796
381 610
382 748
383 767
384 769
385 813
386 546
387 728
388 777
389 840
390 781
391 626
392 785
393 648
394 789
395 791
396 688
397 795
398 814
399 799
400 686
401 640
402 868
403 844
404 760
405 836
406 650
407 756
408 817
409 790
410 821
411 676
412 780
413 827
414 700
415 915
416 666
417 812
418 931
419 839
420 841
421 546
422 845
423 847
424 868
425 851
426 704
427 855
428 784
429 938
430 861
431 660
432 882
433 850
434 869
435 746
436 735
437 875
438 824
439 858
440 931
441 756
442 760
443 854
444 889
445 891
446 714
447 895
448 920
449 792
450 852
451 784
452 905
453 907
454 980
455 856
456 628
457 915
458 917
459 919
460 896
461 777
462 1010
463 817
464 948
465 931
466 746
467 1008
468 937
469 888
470 806
471 740
472 896
473 1034
474 970
475 951
476 762
477 818
478 957
479 988
480 1036
481 770
482 965
483 940
484 900
485 992
486 819
487 975
488 924
489 920
490 962
491 676
492 962
493 1064
494 989
495 1152
496 794
497 995
498 854
499 999
500 1001
501 784
502 970
503 980
504 1009
505 866
506 896
507 960
508 1017
509 1019
510 1021
511 861
512 903
513 1027
514 1029
515 1012
516 836
517 1130
518 1084
519 952
520 1041
521 834
522 1045
523 984
524 1020
525 1051
526 686
527 1055
528 1154
529 1078
530 1022
531 850
532 1148
533 900
534 1050
535 1092
536 884
537 1075
538 1077
539 1197
540 880
541 896
542 1112
543 1087
544 1110
545 1092
546 868
547 938
548 1097
549 1099
550 1202
551 882
552 1105
553 1140
554 950
555 1111
556 890
557 1048
558 1204
559 1078
560 1121
561 903
562 1125
563 1127
564 1080
565 1100
566 906
567 1135
568 974
569 1118
570 1141
571 980
572 1250
573 1147
574 1080
575 986
576 922
577 1155
578 1157
579 1159
580 1161
581 930
582 998
583 1188
584 1281
585 1171
586 987
587 1228
588 1134
589 1008
590 1216
591 896
592 1210
593 1187
594 1298
595 1150
596 820
597 1288
598 1170
599 1199
600 1201
601 962
602 1140
603 1034
604 1188
605 1322
606 960
607 1240
608 1144
609 1219
610 1204
611 1029
612 1225
613 1227
614 1229
615 1231
616 1072
617 1036
618 1237
619 1239
620 1241
621 948
622 1245
623 1344
624 1070
625 1176
626 980
627 1407
628 1257
629 1259
630 1261
631 868
632 1232
633 1324
634 1269
635 1250
636 1176
637 1275
638 1188
639 1258
640 1212
641 1026
642 1208
643 1287
644 1289
645 1106
646 1008
647 1260
648 1274
649 1540
650 1276
651 1040
652 1118
653 1307
654 1288
655 1311
656 1088
657 1270
658 1317
659 1032
660 1463
661 1092
662 1428
663 1327
664 1368
665 1331
666 916
667 1358
668 1364
669 1339
670 1341
671 1168
672 1345
673 1154
674 1349
675 1372
676 1024
677 1380
678 1284
679 1420
680 1166
681 1090
682 1490
683 1400
684 1369
685 1371
686 1155
687 1178
688 1400
689 1379
690 1406
691 1106
692 1385
693 1408
694 1190
695 1391
696 1114
697 1320
698 1397
699 1399
700 1401
701 1064
702 1468
703 1407
704 1456
705 1411
706 1130
707 1415
708 1247
709 1419
710 1365
711 1197
712 1425
713 1427
714 1540
715 1332
716 1092
717 1408
718 1400
719 1390
720 1441
721 1154
722 1238
723 1470
724 1449
725 1516
726 1264
727 1456
728 1457
729 1240
730 1496
731 1170
732 1465
733 1414
734 1469
735 1392
736 1050
737 1610
738 1520
739 1479
740 1596
741 1186
742 1462
743 1274
744 1400
745 1491
746 1194
747 1495
748 1728
749 1499
750 1260
751 1202
752 1505
753 1647
754 1428
755 1511
756 1210
757 1300
758 1540
759 1658
760 1521
761 1176
762 1470
763 1554
764 1310
765 1531
766 1316
767 1512
768 1537
769 1570
770 1641
771 1106
772 1545
773 1464
774 1549
775 1596
776 1242
777 1592
778 1264
779 1680
780 1561
781 1330
782 1540
783 1567
784 1540
785 1346
786 1300
787 1575
788 1554
789 1579
790 1612
791 1232
792 1512
793 1564
794 1660
795 1496
796 1274
797 1595
798 1597
799 1370
800 1601
801 1282
802 1605
803 1754
804 1568
805 1736
806 1118
807 1615
808 1617
809 1619
810 1586
811 1260
812 1520
813 1394
814 1778
815 1631
816 1306
817 1708
818 1764
819 1668
820 1372
821 1314
822 1645
823 1647
824 1688
825 1802
826 1322
827 1418
828 1690
829 1560
830 1572
831 1428
832 1665
833 1694
834 1430
835 1671
836 1554
837 1650
838 1677
839 1679
840 1756
841 1156
842 1685
843 1630
844 1820
845 1666
846 1280
847 1807
848 1454
849 1596
850 1701
851 1364
852 1660
853 1707
854 1709
855 1505
856 1370
857 1848
858 1874
859 1719
860 1746
861 1449
862 1478
863 1664
864 1729
865 1731
866 1386
867 1760
868 1644
869 1620
870 1876
871 1408
872 1745
873 1747
874 1690
875 1751
876 1204
877 1755
878 1694
879 1759
880 1792
881 1410
882 1765
883 1624
884 1769
885 1742
886 1596
887 1715
888 1777
889 1779
890 1512
891 1552
892 1785
893 1740
894 1789
895 1791
896 1540
897 1456
898 1797
899 1799
900 1801
901 1442
902 1995
903 1807
904 1591
905 1750
906 1380
907 1750
908 1817
909 2072
910 1821
911 1302
912 1860
913 1994
914 1720
915 1806
916 1456
917 1862
918 1584
919 1839
920 1841
921 1474
922 2013
923 1900
924 2018
925 1512
926 1482
927 1855
928 1857
929 1859
930 1836
931 1408
932 1656
933 1820
934 1820
935 2212
936 1470
937 1850
938 1850
939 1610
940 1881
941 1506
942 1885
943 1887
944 1788
945 1891
946 1440
947 1895
948 1904
949 1899
950 1901
951 1522
952 1905
953 1677
954 1909
955 1996
956 1530
957 2090
958 1917
959 1919
960 1672
961 1764
962 1925
963 1824
964 1898
965 1792
966 1546
967 1620
968 2114
969 1898
970 1941
971 1554
972 1945
973 1984
974 1792
975 1900
976 1540
977 1955
978 2044
979 2138
980 1961
981 1348
982 1776
983 1967
984 1969
985 1936
986 1659
987 2128
988 1694
989 1979
990 2162
991 1586
992 1985
993 1960
994 1918
995 1706
996 1594
997 2052
998 1930
999 1911
1000 2156