1 1
2 2
3 3
4 5
5 9
6 4
7 7
8 13
9 6
10 11
11 20
12 10
13 18
14 33
15 17
16 31
17 57
18 8
19 15
20 27
21 14
22 25
23 46
24 24
25 44
26 81
27 12
28 22
29 40
30 21
31 38
32 70
33 37
34 68
35 125
36 19
37 35
38 64
39 34
40 62
41 114
42 61
43 112
44 206
45 32
46 59
47 108
48 58
49 106
50 195
51 105
52 193
53 355
54 16
55 29
56 53
57 28
58 51
59 94
60 50
61 92
62 169
63 26
64 48
65 88
66 47
67 86
68 158
69 85
70 156
71 287
72 45
73 83
74 152
75 82
76 150
77 276
78 149
79 274
80 504
81 23
82 42
83 77
84 41
85 75
86 138
87 74
88 136
89 250
90 39
91 72
92 132
93 71
94 130
95 239
96 129
97 237
98 436
99 69
100 127
101 233
102 126
103 231
104 425
105 230
106 423
107 778
108 36
109 66
110 121
111 65
112 119
113 219
114 118
115 217
116 399
117 63
118 116
119 213
120 115
121 211
122 388
123 210
124 386
125 710
126 113
127 208
128 382
129 207
130 380
131 699
132 379
133 697
134 1282
135 60
136 110
137 202
138 109
139 200
140 368
141 199
142 366
143 673
144 107
145 197
146 362
147 196
148 360
149 662
150 359
151 660
152 1214
153 194
154 357
155 656
156 356
157 654
158 1203
159 653
160 1201
161 2209
162 30
163 55
164 101
165 54
166 99
167 182
168 98
169 180
170 331
171 52
172 96
173 176
174 95
175 174
176 320
177 173
178 318
179 585
180 93
181 171
182 314
183 170
184 312
185 574
186 311
187 572
188 1052
189 49
190 90
191 165
192 89
193 163
194 300
195 162
196 298
197 548
198 87
199 160
200 294
201 159
202 292
203 537
204 291
205 535
206 984
207 157
208 289
209 531
210 288
211 529
212 973
213 528
214 971
215 1786
216 84
217 154
218 283
219 153
220 281
221 517
222 280
223 515
224 947
225 151
226 278
227 511
228 277
229 509
230 936
231 508
232 934
233 1718
234 275
235 506
236 930
237 505
238 928
239 1707
240 927
241 1705
242 3136
243 43
244 79
245 145
246 78
247 143
248 263
249 142
250 261
251 480
252 76
253 140
254 257
255 139
256 255
257 469
258 254
259 467
260 859
261 137
262 252
263 463
264 251
265 461
266 848
267 460
268 846
269 1556
270 73
271 134
272 246
273 133
274 244
275 449
276 243
277 447
278 822
279 131
280 241
281 443
282 240
283 441
284 811
285 440
286 809
287 1488
288 238
289 438
290 805
291 437
292 803
293 1477
294 802
295 1475
296 2713
297 128
298 235
299 432
300 234
301 430
302 791
303 429
304 789
305 1451
306 232
307 427
308 785
309 426
310 783
311 1440
312 782
313 1438
314 2645
315 424
316 780
317 1434
318 779
319 1432
320 2634
321 1431
322 2632
323 4841
324 67
325 123
326 226
327 122
328 224
329 412
330 223
331 410
332 754
333 120
334 221
335 406
336 220
337 404
338 743
339 403
340 741
341 1363
342 218
343 401
344 737
345 400
346 735
347 1352
348 734
349 1350
350 2483
351 117
352 215
353 395
354 214
355 393
356 723
357 392
358 721
359 1326
360 212
361 390
362 717
363 389
364 715
365 1315
366 714
367 1313
368 2415
369 387
370 712
371 1309
372 711
373 1307
374 2404
375 1306
376 2402
377 4418
378 209
379 384
380 706
381 383
382 704
383 1295
384 703
385 1293
386 2378
387 381
388 701
389 1289
390 700
391 1287
392 2367
393 1286
394 2365
395 4350
396 698
397 1284
398 2361
399 1283
400 2359
401 4339
402 2358
403 4337
404 111
405 204
406 375
407 203
408 373
409 686
410 372
411 684
412 1258
413 201
414 370
415 680
416 369
417 678
418 1247
419 677
420 1245
421 2290
422 367
423 675
424 1241
425 674
426 1239
427 2279
428 1238
429 2277
430 4188
431 198
432 364
433 669
434 363
435 667
436 1227
437 666
438 1225
439 2253
440 361
441 664
442 1221
443 663
444 1219
445 2242
446 1218
447 2240
448 4120
449 661
450 1216
451 2236
452 1215
453 2234
454 4109
455 2233
456 4107
457 358
458 658
459 1210
460 657
461 1208
462 2222
463 1207
464 2220
465 4083
466 655
467 1205
468 2216
469 1204
470 2214
471 4072
472 2213
473 4070
474 1202
475 2211
476 4066
477 2210
478 4064
479 4063
480 56
481 103
482 189
483 102
484 187
485 344
486 186
487 342
488 629
489 100
490 184
491 338
492 183
493 336
494 618
495 335
496 616
497 1133
498 181
499 333
500 612
501 332
502 610
503 1122
504 609
505 1120
506 2060
507 97
508 178
509 327
510 177
511 325
512 598
513 324
514 596
515 1096
516 175
517 322
518 592
519 321
520 590
521 1085
522 589
523 1083
524 1992
525 319
526 587
527 1079
528 586
529 1077
530 1981
531 1076
532 1979
533 3640
534 172
535 316
536 581
537 315
538 579
539 1065
540 578
541 1063
542 1955
543 313
544 576
545 1059
546 575
547 1057
548 1944
549 1056
550 1942
551 3572
552 573
553 1054
554 1938
555 1053
556 1936
557 3561
558 1935
559 3559
560 91
561 167
562 307
563 166
564 305
565 561
566 304
567 559
568 1028
569 164
570 302
571 555
572 301
573 553
574 1017
575 552
576 1015
577 1867
578 299
579 550
580 1011
581 549
582 1009
583 1856
584 1008
585 1854
586 3410
587 161
588 296
589 544
590 295
591 542
592 997
593 541
594 995
595 1830
596 293
597 539
598 991
599 538
600 989
601 1819
602 988
603 1817
604 3342
605 536
606 986
607 1813
608 985
609 1811
610 3331
611 1810
612 3329
613 290
614 533
615 980
616 532
617 978
618 1799
619 977
620 1797
621 3305
622 530
623 975
624 1793
625 974
626 1791
627 3294
628 1790
629 3292
630 972
631 1788
632 3288
633 1787
634 3286
635 3285
636 155
637 285
638 524
639 284
640 522
641 960
642 521
643 958
644 1762
645 282
646 519
647 954
648 518
649 952
650 1751
651 951
652 1749
653 3217
654 516
655 949
656 1745
657 948
658 1743
659 3206
660 1742
661 3204
662 279
663 513
664 943
665 512
666 941
667 1731
668 940
669 1729
670 3180
671 510
672 938
673 1725
674 937
675 1723
676 3169
677 1722
678 3167
679 935
680 1720
681 3163
682 1719
683 3161
684 3160
685 507
686 932
687 1714
688 931
689 1712
690 3149
691 1711
692 3147
693 929
694 1709
695 3143
696 1708
697 3141
698 3140
699 1706
700 3138
701 3137
702 80
703 147
704 270
705 146
706 268
707 493
708 267
709 491
710 903
711 144
712 265
713 487
714 264
715 485
716 892
717 484
718 890
719 1637
720 262
721 482
722 886
723 481
724 884
725 1626
726 883
727 1624
728 2987
729 141
730 259
731 476
732 258
733 474
734 872
735 473
736 870
737 1600
738 256
739 471
740 866
741 470
742 864
743 1589
744 863
745 1587
746 2919
747 468
748 861
749 1583
750 860
751 1581
752 2908
753 1580
754 2906
755 5345
756 253
757 465
758 855
759 464
760 853
761 1569
762 852
763 1567
764 2882
765 462
766 850
767 1563
768 849
769 1561
770 2871
771 1560
772 2869
773 5277
774 847
775 1558
776 2865
777 1557
778 2863
779 5266
780 2862
781 5264
782 135
783 248
784 456
785 247
786 454
787 835
788 453
789 833
790 1532
791 245
792 451
793 829
794 450
795 827
796 1521
797 826
798 1519
799 2794
800 448
801 824
802 1515
803 823
804 1513
805 2783
806 1512
807 2781
808 5115
809 242
810 445
811 818
812 444
813 816
814 1501
815 815
816 1499
817 2757
818 442
819 813
820 1495
821 812
822 1493
823 2746
824 1492
825 2744
826 5047
827 810
828 1490
829 2740
830 1489
831 2738
832 5036
833 2737
834 5034
835 439
836 807
837 1484
838 806
839 1482
840 2726
841 1481
842 2724
843 5010
844 804
845 1479
846 2720
847 1478
848 2718
849 4999
850 2717
851 4997
852 1476
853 2715
854 4993
855 2714
856 4991
857 4990
858 236
859 434
860 798
861 433
862 796
863 1464
864 795
865 1462
866 2689
867 431
868 793
869 1458
870 792
871 1456
872 2678
873 1455
874 2676
875 4922
876 790
877 1453
878 2672
879 1452
880 2670
881 4911
882 2669
883 4909
884 428
885 787
886 1447
887 786
888 1445
889 2658
890 1444
891 2656
892 4885
893 784
894 1442
895 2652
896 1441
897 2650
898 4874
899 2649
900 4872
901 1439
902 2647
903 4868
904 2646
905 4866
906 4865
907 781
908 1436
909 2641
910 1435
911 2639
912 4854
913 2638
914 4852
915 1433
916 2636
917 4848
918 2635
919 4846
920 4845
921 2633
922 4843
923 4842
924 124
925 228
926 419
927 227
928 417
929 767
930 416
931 765
932 1407
933 225
934 414
935 761
936 413
937 759
938 1396
939 758
940 1394
941 2564
942 411
943 756
944 1390
945 755
946 1388
947 2553
948 1387
949 2551
950 4692
951 222
952 408
953 750
954 407
955 748
956 1376
957 747
958 1374
959 2527
960 405
961 745
962 1370
963 744
964 1368
965 2516
966 1367
967 2514
968 4624
969 742
970 1365
971 2510
972 1364
973 2508
974 4613
975 2507
976 4611
977 402
978 739
979 1359
980 738
981 1357
982 2496
983 1356
984 2494
985 4587
986 736
987 1354
988 2490
989 1353
990 2488
991 4576
992 2487
993 4574
994 1351
995 2485
996 4570
997 2484
998 4568
999 4567
1000 216