0 1
1 1
2 2
3 3
4 5
5 5
6 8
7 7
8 15
9 13
10 17
11 13
12 12
13 17
14 30
15 17
16 20
17 19
18 26
19 23
20 29
21 25
22 34
23 37
24 57
25 25
26 59
27 45
28 28
29 43
30 81
31 43
32 55
33 113
34 34
35 41
36 82
37 41
38 39
39 135
40 40
41 43
42 124
43 71
44 108
45 49
46 76
47 73
48 69
49 77
50 121
51 81
52 100
53 61
54 151
55 55
56 136
57 107
58 65
59 59
60 212
61 181
62 181
63 67
64 74
65 83
66 103
67 67
68 101
69 69
70 70
71 131
72 180
73 119
74 119
75 87
76 119
77 189
78 181
79 79
80 195
81 151
82 91
83 91
84 237
85 147
86 94
87 157
88 91
89 95
90 162
91 107
92 182
93 201
94 147
95 127
96 115
97 99
98 171
99 185
100 108
101 209
102 183
103 129
104 226
105 153
106 185
107 115
108 196
109 117
110 167
111 195
112 148
113 165
114 257
115 183
116 125
117 273
118 313
119 179
120 212
121 245
122 423
123 187
124 222
125 133
126 221
127 155
128 190
129 129
130 268
131 139
132 286
133 183
134 262
135 135
136 237
137 137
138 334
139 153
140 292
141 165
142 153
143 253
144 228
145 229
146 339
147 167
148 279
149 187
150 207
151 167
152 368
153 161
154 253
155 211
156 334
157 213
158 292
159 183
160 254
161 197
162 369
163 319
164 270
165 183
166 470
167 193
168 240
169 421
170 238
171 385
172 230
173 349
174 455
175 197
176 342
177 209
178 194
179 325
180 329
181 187
182 260
183 287
184 333
185 193
186 262
187 233
188 218
189 189
190 247
191 217
192 553
193 369
194 300
195 365
196 383
197 265
198 484
199 229
200 212
201 257
202 369
203 255
204 363
205 363
206 350
207 209
208 476
209 439
210 233
211 357
212 215
213 337
214 272
215 419
216 433
217 333
218 361
219 311
220 875
221 257
222 512
223 317
224 804
225 365
226 845
227 281
228 376
229 229
230 772
231 347
232 682
233 289
234 329
235 345
236 281
237 629
238 527
239 471
240 244
241 643
242 503
243 473
244 607
245 269
246 246
247 311
248 437
249 251
250 604
251 251
252 662
253 305
254 570
255 347
256 306
257 259
258 810
259 563
260 506
261 341
262 318
263 437
264 418
265 495
266 455
267 365
268 362
269 557
270 547
271 385
272 497
273 327
274 652
275 763
276 448
277 443
278 514
279 297
280 358
281 327
282 585
283 329
284 562
285 623
286 580
287 571
288 531
289 407
290 468
291 625
292 535
293 301
294 693
295 569
296 964
297 439
298 765
299 441
300 319
301 409
302 358
303 371
304 740
305 481
306 944
307 365
308 382
309 313
310 770
311 377
312 531
313 327
314 716
315 443
316 1274
317 453
318 689
319 439
320 825
321 613
322 430
323 539
324 369
325 591
326 571
327 533
328 521
329 407
330 780
331 417
332 631
333 343
334 349
335 353
336 752
337 337
338 353
339 419
340 891
341 377
342 647
343 549
344 557
345 541
346 575
347 859
348 743
349 573
350 745
351 385
352 377
353 385
354 366
355 359
356 438
357 717
358 799
359 361
360 594
361 361
362 561
363 389
364 472
365 621
366 868
367 393
368 921
369 559
370 615
371 849
372 1043
373 659
374 700
375 449
376 379
377 377
378 1309
379 425
380 894
381 589
382 623
383 515
384 615
385 405
386 633
387 491
388 652
389 411
390 848
391 391
392 438
393 657
394 536
395 925
396 1096
397 427
398 687
399 659
400 535
401 787
402 788
403 403
404 504
405 455
406 730
407 873
408 1336
409 595
410 464
411 461
412 752
413 471
414 873
415 475
416 1005
417 425
418 735
419 421
420 977
421 665
422 571
423 685
424 590
425 733
426 527
427 919
428 841
429 505
430 807
431 901
432 786
433 449
434 849
435 437
436 436
437 847
438 446
439 585
440 796
441 441
442 736
443 743
444 788
445 445
446 1043
447 569
448 904
449 629
450 767
451 603
452 614
453 493
454 495
455 531
456 497
457 1335
458 1301
459 785
460 654
461 641
462 1171
463 491
464 713
465 745
466 639
467 577
468 675
469 491
470 978
471 585
472 820
473 707
474 615
475 483
476 680
477 685
478 1036
479 555
480 500
481 663
482 972
483 831
484 854
485 1359
486 1079
487 541
488 659
489 863
490 1093
491 577
492 1036
493 833
494 925
495 551
496 733
497 615
498 860
499 923
500 1368
501 501
502 995
503 515
504 1055
505 529
506 674
507 739
508 809
509 987
510 691
511 607
512 551
513 849
514 1073
515 591
516 995
517 1129
518 998
519 561
520 1087
521 673
522 1356
523 627
524 998
525 951
526 965
527 597
528 1583
529 713
530 1146
531 957
532 583
533 671
534 736
535 791
536 740
537 1243
538 778
539 823
540 1050
541 615
542 984
543 657
544 698
545 1161
546 664
547 553
548 596
549 909
550 1255
551 749
552 1144
553 905
554 819
555 573
556 1519
557 643
558 1509
559 559
560 1125
561 785
562 1235
563 1175
564 596
565 1337
566 700
567 945
568 1316
569 767
570 907
571 963
572 1067
573 955
574 709
575 1459
576 1343
577 577
578 953
579 1321
580 1646
581 599
582 703
583 1179
584 669
585 661
586 613
587 619
588 936
589 793
590 1906
591 623
592 604
593 647
594 1045
595 1017
596 914
597 937
598 613
599 799
600 1684
601 665
602 1590
603 737
604 1042
605 833
606 851
607 611
608 945
609 609
610 798
611 855
612 1538
613 637
614 1055
615 741
616 1309
617 907
618 706
619 1141
620 829
621 621
622 950
623 643
624 780
625 625
626 1561
627 993
628 701
629 1229
630 1730
631 651
632 1211
633 817
634 1275
635 851
636 1692
637 947
638 1032
639 889
640 1270
641 857
642 912
643 713
644 866
645 853
646 890
647 671
648 1278
649 1149
650 1739
651 679
652 1084
653 697
654 1350
655 785
656 1451
657 1081
658 817
659 707
660 1134
661 901
662 1124
663 1437
664 982
665 787
666 1115
667 729
668 890
669 1069
670 1925
671 1023
672 1690
673 677
674 2148
675 1005
676 1842
677 911
678 1346
679 1305
680 837
681 779
682 1614
683 1103
684 1399
685 1465
686 697
687 749
688 1429
689 855
690 1353
691 1043
692 803
693 1363
694 1747
695 1245
696 1282
697 891
698 1030
699 1067
700 1239
701 951
702 1408
703 735
704 1064
705 1145
706 1440
707 739
708 1141
709 791
710 1742
711 751
712 1491
713 1189
714 1639
715 1313
716 1203
717 1093
718 1693
719 1367
720 2276
721 1583
722 1168
723 847
724 2340
725 1031
726 961
727 775
728 970
729 1183
730 1176
731 771
732 998
733 767
734 1767
735 941
736 2040
737 1121
738 1225
739 755
740 1229
741 999
742 1442
743 1183
744 1240
745 1847
746 1306
747 823
748 1580
749 759
750 1125
751 1421
752 1653
753 799
754 1407
755 1259
756 1652
757 1807
758 2640
759 1131
760 2163
761 927
762 997
763 837
764 1078
765 1617
766 1668
767 1027
768 827
769 1321
770 1318
771 1201
772 909
773 2319
774 789
775 867
776 878
777 985
778 2045
779 827
780 1071
781 837
782 1563
783 865
784 1029
785 1011
786 1566
787 1219
788 1472
789 1021
790 1519
791 1221
792 1719
793 793
794 1520
795 927
796 2274
797 1049
798 1165
799 805
800 1813
801 1181
802 1168
803 1373
804 1512
805 997
806 1679
807 1103
808 941
809 1111
810 1607
811 839
812 1396
813 1089
814 1479
815 901
816 1277
817 1365
818 973
819 1543
820 953
821 1001
822 1941
823 823
824 2998
825 1625
826 1552
827 2249
828 1211
829 851
830 1545
831 923
832 936
833 883
834 1068
835 853
836 1313
837 1007
838 2491
839 973
840 1572
841 1209
842 2017
843 1801
844 1182
845 1147
846 3284
847 849
848 1067
849 1839
850 1508
851 1457
852 1399
853 1031
854 1661
855 855
856 1297
857 857
858 1514
859 869
860 2076
861 1411
862 2043
863 1127
864 1545
865 933
866 2273
867 1779
868 1334
869 873
870 1574
871 1079
872 2388
873 1059
874 1646
875 1073
876 1473
877 1199
878 2022
879 1219
880 1165
881 883
882 2777
883 883
884 2779
885 935
886 1627
887 887
888 981
889 1459
890 2558
891 979
892 1761
893 1241
894 1448
895 897
896 1592
897 1831
898 1983
899 1171
900 1709
901 1545
902 1999
903 903
904 1396
905 1043
906 1610
907 907
908 2196
909 909
910 1354
911 1349
912 2060
913 1093
914 2453
915 915
916 2505
917 929
918 1384
919 1115
920 1272
921 1499
922 1810
923 2417
924 1221
925 1147
926 1858
927 1321
928 1923
929 951
930 1622
931 1093
932 1412
933 1187
934 3044
935 1853
936 1045
937 1037
938 1471
939 939
940 1457
941 979
942 944
943 1223
944 1894
945 1315
946 2189
947 957
948 1542
949 1559
950 1182
951 1221
952 1024
953 2613
954 3367
955 1173
956 2643
957 1137
958 2030
959 1727
960 2297
961 1003
962 1008
963 1597
964 1189
965 979
966 1276
967 1081
968 1755
969 1035
970 1927
971 1517
972 1359
973 1029
974 2052
975 1207
976 1898
977 1021
978 1692
979 979
980 1996
981 1009
982 1401
983 1765
984 2539
985 1601
986 2278
987 1761
988 1461
989 1647
990 1062
991 1337
992 1594
993 1839
994 1598
995 1049
996 1768
997 1105
998 1353
999 1621
1000 1175