1 0
2 0
3 1
4 3
5 2
6 4
7 10
8 3
9 13
10 15
11 7
12 7
13 16
14 16
15 27
16 25
17 20
18 13
19 18
20 30
21 29
22 30
23 32
24 51
25 33
26 34
27 37
28 44
29 21
30 53
31 27
32 39
33 62
34 35
35 69
36 28
37 43
38 43
39 93
40 89
41 74
42 42
43 94
44 62
45 81
46 54
47 35
48 73
49 98
50 74
51 110
52 101
53 67
54 86
55 120
56 143
57 121
58 109
59 96
60 89
61 84
62 135
63 102
64 139
65 108
66 159
67 99
68 108
69 158
70 112
71 176
72 197
73 127
74 112
75 106
76 207
77 175
78 94
79 153
80 134
81 152
82 114
83 169
84 110
85 153
86 199
87 166
88 114
89 226
90 124
91 212
92 263
93 162
94 196
95 163
96 271
97 259
98 299
99 156
100 169
101 132
102 273
103 254
104 307
105 147
106 196
107 272
108 295
109 259
110 176
111 223
112 154
113 247
114 188
115 122
116 279
117 218
118 310
119 309
120 244
121 198
122 236
123 328
124 274
125 131
126 221
127 236
128 389
129 239
130 213
131 229
132 348
133 239
134 171
135 284
136 247
137 397
138 241
139 393
140 377
141 187
142 323
143 266
144 303
145 249
146 451
147 288
148 415
149 268
150 451
151 285
152 363
153 203
154 471
155 285
156 328
157 281
158 435
159 269
160 364
161 421
162 405
163 259
164 341
165 531
166 517
167 284
168 334
169 250
170 487
171 470
172 256
173 425
174 298
175 355
176 554
177 278
178 407
179 375
180 347
181 369
182 393
183 287
184 579
185 504
186 535
187 376
188 284
189 364
190 463
191 347
192 560
193 258
194 481
195 566
196 613
197 237
198 392
199 571
200 648
201 607
202 305
203 524
204 369
205 528
206 583
207 388
208 608
209 606
210 324
211 375
212 512
213 308
214 620
215 703
216 359
217 453
218 473
219 707
220 567
221 442
222 489
223 598
224 471
225 630
226 354
227 707
228 757
229 493
230 511
231 503
232 568
233 353
234 539
235 417
236 779
237 413
238 727
239 598
240 635
241 740
242 314
243 534
244 491
245 761
246 715
247 520
248 573
249 506
250 740
251 414
252 593
253 738
254 525
255 746
256 764
257 456
258 528
259 801
260 463
261 575
262 648
263 493
264 583
265 838
266 535
267 729
268 604
269 471
270 837
271 468
272 575
273 531
274 620
275 511
276 519
277 783
278 583
279 423
280 624
281 955
282 566
283 821
284 424
285 613
286 685
287 560
288 764
289 615
290 921
291 720
292 914
293 942
294 765
295 540
296 977
297 549
298 957
299 856
300 625
301 666
302 1021
303 661
304 676
305 494
306 553
307 980
308 578
309 1063
310 666
311 1075
312 915
313 759
314 675
315 910
316 613
317 992
318 846
319 509
320 947
321 522
322 649
323 913
324 715
325 1082
326 536
327 745
328 709
329 1141
330 922
331 622
332 1020
333 781
334 954
335 593
336 944
337 639
338 1060
339 566
340 763
341 772
342 980
343 1153
344 514
345 1117
346 951
347 548
348 780
349 987
350 1162
351 647
352 787
353 841
354 804
355 774
356 1181
357 1107
358 921
359 1147
360 1063
361 710
362 1064
363 1259
364 1172
365 784
366 824
367 1251
368 843
369 828
370 815
371 812
372 1212
373 973
374 663
375 838
376 1226
377 1045
378 961
379 1404
380 855
381 1094
382 1244
383 764
384 1289
385 845
386 1234
387 698
388 910
389 836
390 1298
391 724
392 1351
393 1193
394 852
395 1136
396 915
397 925
398 1239
399 508
400 1013
401 856
402 1351
403 920
404 1351
405 1174
406 685
407 906
408 1135
409 901
410 1346
411 885
412 1387
413 1196
414 730
415 782
416 1073
417 1495
418 892
419 1372
420 1509
421 1417
422 1071
423 1288
424 1302
425 1006
426 1491
427 1442
428 1202
429 687
430 1571
431 961
432 978
433 975
434 1557
435 719
436 982
437 1007
438 638
439 818
440 926
441 1428
442 1529
443 816
444 1627
445 822
446 1242
447 1005
448 1635
449 980
450 759
451 1043
452 1126
453 1568
454 1588
455 1061
456 1020
457 1080
458 1049
459 1006
460 1533
461 1037
462 887
463 1430
464 719
465 930
466 1228
467 1021
468 1362
469 1606
470 792
471 1134
472 1434
473 1792
474 743
475 1254
476 1153
477 1302
478 970
479 1610
480 1683
481 829
482 1752
483 1268
484 1507
485 1141
486 1676
487 1143
488 1321
489 980
490 817
491 1120
492 1664
493 959
494 1797
495 1618
496 884
497 1145
498 1457
499 1222
500 674
501 1356
502 1193
503 1802
504 1227
505 1050
506 1780
507 1855
508 921
509 1130
510 1178
511 1708
512 1509
513 1175
514 1847
515 840
516 1001
517 1423
518 1223
519 1636
520 1104
521 1209
522 1153
523 1342
524 1615
525 1256
526 1796
527 1100
528 1645
529 1856
530 1465
531 980
532 1904
533 1318
534 1097
535 1122
536 1991
537 1104
538 1454
539 1230
540 973
541 1436
542 1757
543 1329
544 1732
545 2031
546 1040
547 1283
548 1922
549 1338
550 1963
551 1617
552 1298
553 2059
554 1844
555 1680
556 1127
557 1152
558 1827
559 1038
560 1261
561 2067
562 2123
563 1546
564 1204
565 1363
566 1099
567 2111
568 1514
569 2019
570 2012
571 1395
572 2095
573 1086
574 1644
575 1070
576 1652
577 1837
578 1203
579 1836
580 1255
581 1674
582 1170
583 2163
584 2024
585 1123
586 1461
587 1405
588 2078
589 2009
590 1450
591 1218
592 2087
593 1426
594 2137
595 1410
596 1441
597 2197
598 1839
599 1952
600 2048
601 1582
602 1250
603 1152
604 1188
605 1708
606 2171
607 2162
608 1586
609 1583
610 2261
611 1494
612 1411
613 2291
614 1508
615 1793
616 2222
617 1478
618 1329
619 1538
620 2268
621 1120
622 1449
623 1331
624 972
625 2195
626 1596
627 2004
628 1951
629 1113
630 1512
631 1215
632 2329
633 2429
634 1603
635 2425
636 2401
637 1578
638 1463
639 2047
640 1935
641 1389
642 1640
643 2318
644 1404
645 2279
646 2461
647 1536
648 1656
649 2082
650 1073
651 1157
652 1996
653 2369
654 2110
655 1623
656 1644
657 2549
658 1626
659 1535
660 2392
661 2115
662 1217
663 1441
664 2323
665 1405
666 2166
667 1723
668 1618
669 1382
670 2418
671 2494
672 1304
673 2054
674 1664
675 2279
676 1833
677 1637
678 1498
679 2006
680 2611
681 2432
682 1147
683 1534
684 1618
685 1721
686 2532
687 2104
688 1398
689 1715
690 1721
691 2553
692 1697
693 1536
694 1556
695 2153
696 1666
697 1971
698 2052
699 2622
700 2134
701 1085
702 2737
703 2375
704 2603
705 1781
706 2700
707 1450
708 2177
709 2195
710 2624
711 2634
712 2777
713 1689
714 1544
715 2677
716 1469
717 1407
718 1756
719 2357
720 1796
721 1795
722 2234
723 2678
724 1725
725 2690
726 1894
727 1532
728 2684
729 2661
730 1449
731 1836
732 1960
733 1803
734 1837
735 1804
736 2388
737 1394
738 2009
739 1856
740 2905
741 1452
742 1901
743 2140
744 1926
745 2434
746 1724
747 2604
748 1869
749 1775
750 2887
751 1459
752 2393
753 2859
754 1964
755 1884
756 1651
757 1886
758 1834
759 2464
760 1576
761 2196
762 2967
763 2859
764 1457
765 1936
766 1566
767 2715
768 2665
769 1520
770 1892
771 2228
772 2368
773 2013
774 3039
775 1284
776 2433
777 2826
778 1672
779 3033
780 2864
781 1962
782 2190
783 2760
784 1454
785 2369
786 2599
787 1945
788 1791
789 3093
790 2905
791 1994
792 1643
793 2059
794 3072
795 1196
796 2316
797 2960
798 1394
799 2403
800 1652
801 3033
802 1586
803 1948
804 3047
805 3061
806 2072
807 2610
808 1784
809 1609
810 2593
811 1968
812 2172
813 2784
814 3059
815 3181
816 1509
817 2039
818 2670
819 2974
820 1281
821 2655
822 3109
823 2939
824 2738
825 2017
826 1795
827 3211
828 2789
829 1479
830 2132
831 2110
832 2132
833 3203
834 1737
835 2001
836 1719
837 2941
838 1658
839 1929
840 3293
841 1556
842 2238
843 2462
844 2229
845 2141
846 2566
847 1784
848 2951
849 3162
850 1703
851 2205
852 2197
853 3407
854 2215
855 2170
856 1828
857 3281
858 3260
859 1991
860 2201
861 1958
862 2968
863 1724
864 2656
865 2189
866 1968
867 3463
868 1888
869 3323
870 2676
871 1772
872 3272
873 1660
874 2284
875 2352
876 3224
877 2218
878 3362
879 2245
880 3081
881 1537
882 3438
883 3483
884 3148
885 2079
886 2316
887 3344
888 2251
889 2782
890 2432
891 3260
892 2212
893 3175
894 1845
895 2450
896 2456
897 3381
898 3547
899 1831
900 2396
901 2400
902 3469
903 2994
904 2384
905 2187
906 2893
907 1980
908 1969
909 3623
910 3449
911 3585
912 2965
913 3028
914 1968
915 2462
916 2405
917 2125
918 3518
919 3240
920 2454
921 2487
922 2400
923 2395
924 3323
925 2354
926 2195
927 3669
928 3015
929 3224
930 2216
931 3348
932 2146
933 1891
934 2916
935 2092
936 3413
937 1695
938 2539
939 1680
940 1880
941 2414
942 3761
943 3018
944 3801
945 2212
946 2132
947 2642
948 3587
949 2124
950 3396
951 2470
952 3737
953 3656
954 3715
955 2593
956 2741
957 2903
958 2234
959 3893
960 1808
961 2566
962 3751
963 3523
964 3296
965 1938
966 2174
967 3891
968 1973
969 2431
970 3734
971 3736
972 2500
973 3437
974 2146
975 2329
976 2884
977 2495
978 3931
979 2641
980 1990
981 3943
982 2076
983 2301
984 3291
985 2627
986 2449
987 3747
988 3931
989 3985
990 3452
991 2924
992 3660
993 2349
994 2463
995 3698
996 2480
997 3378
998 3012
999 3702
1000 3917