1 1
2 7
3 13
4 35
5 31
6 91
7 57
8 155
9 130
10 217
11 133
12 455
13 183
14 399
15 403
16 651
17 307
18 910
19 381
20 1085
21 741
22 931
23 553
24 2015
25 806
26 1281
27 1210
28 1995
29 871
30 2821
31 993
32 2667
33 1729
34 2149
35 1767
36 4550
37 1407
38 2667
39 2379
40 4805
41 1723
42 5187
43 1893
44 4655
45 4030
46 3871
47 2257
48 8463
49 2850
50 5642
51 3991
52 6405
53 2863
54 8470
55 4123
56 8835
57 4953
58 6097
59 3541
60 14105
61 3783
62 6951
63 7410
64 10795
65 5673
66 12103
67 4557
68 10745
69 7189
70 12369
71 5113
72 20150
73 5403
74 9849
75 10478
76 13335
77 7581
78 16653
79 6321
80 20181
81 11011
82 12061
83 6973
84 25935
85 9517
86 13251
87 11323
88 20615
89 8011
90 28210
91 10431
92 19355
93 12909
94 15799
95 11811
96 34671
97 9507
98 19950
99 17290
100 28210
101 10303
102 27937
103 10713
104 28365
105 22971
106 20041
107 11557
108 42350
109 11991
110 28861
111 18291
112 37107
113 12883
114 34671
115 17143
116 30485
117 23790
118 24787
119 17499
120 62465
121 16226
122 26481
123 22399
124 34755
125 20306
126 51870
127 16257
128 43435
129 24609
130 39711
131 17293
132 60515
133 21717
134 31899
135 37510
136 47585
137 18907
138 50323
139 19461
140 61845
141 29341
142 35791
143 24339
144 84630
145 27001
146 37821
147 37050
148 49245
149 22351
150 73346
151 22953
152 59055
153 39910
154 53067
155 30783
156 83265
157 24807
158 44247
159 37219
160 82677
161 31521
162 77077
163 26733
164 60305
165 53599
166 48811
167 28057
168 114855
169 31110
170 66619
171 49530
172 66255
173 30103
174 79261
175 45942
176 86583
177 46033
178 56077
179 32221
180 141050
181 32943
182 73017
183 49179
184 85715
185 43617
186 90363
187 40831
188 78995
189 68970
190 82677
191 36673
192 140335
193 37443
194 66549
195 73749
196 99750
197 39007
198 121030
199 39801
200 124930
201 59241
202 72121
203 49647
204 139685
205 53413
206 74991
207 71890
208 119133
209 50673
210 160797
211 44733
212 100205
213 66469
214 80899
215 58683
216 187550
217 56601
218 83937
219 70239
220 144305
221 56181
222 128037
223 49953
224 152019
225 104780
226 90181
227 51757
228 173355
229 52671
230 120001
231 98553
232 135005
233 54523
234 166530
235 69967
236 123935
237 82173
238 122493
239 57361
240 262353
241 58323
242 113582
243 99463
244 132405
245 88350
246 156793
247 69723
248 153915
249 90649
250 142142
251 63253
252 259350
253 73549
254 113799
255 123721
256 174251
257 66307
258 172263
259 80199
260 198555
261 113230
262 121051
263 69433
264 267995
265 88753
266 152019
267 104143
268 159495
269 72631
270 262570
271 73713
272 199857
273 135603
274 132349
275 107198
276 251615
277 77007
278 136227
279 129090
280 273885
281 79243
282 205387
283 80373
284 178955
285 153543
286 170373
287 98211
288 346710
289 89030
290 189007
291 123591
292 189105
293 86143
294 259350
295 109771
296 218085
297 160930
298 156457
299 101199
300 366730
301 107901
302 160671
303 133939
304 248031
305 117273
306 279370
307 94557
308 265335
309 139269
310 215481
311 97033
312 368745
313 98283
314 173649
315 229710
316 221235
317 100807
318 260533
319 115843
320 334645
321 150241
322 220647
323 116967
324 385385
325 147498
326 187131
327 155883
328 267065
329 128649
330 375193
331 109893
332 244055
333 182910
334 196399
335 141267
336 482391
337 113907
338 217770
339 167479
340 333095
341 132069
342 346710
343 140050
344 293415
345 222859
346 210721
347 120757
348 396305
349 122151
350 321594
351 221430
352 354711
353 124963
354 322231
355 158503
356 280385
357 227487
358 225547
359 129241
360 624650
361 137922
362 230601
363 210938
364 365085
365 167493
366 344253
367 135057
368 360003
369 223990
370 305319
371 163191
372 451815
373 139503
374 285817
375 263978
376 349835
377 159393
378 482790
379 144021
380 413385
381 211341
382 256711
383 147073
384 564655
385 235011
386 262101
387 246090
388 332745
389 151711
390 516243
391 169771
392 441750
393 224809
394 273049
395 195951
396 605150
397 158007
398 278607
399 282321
400 524706
401 161203
402 414687
403 181719
404 360605
405 341341
406 347529
407 187131
408 618605
409 167691
410 373891
411 245791
412 374955
413 201837
414 503230
415 216163
416 488061
417 252993
418 354711
419 175981
420 803985
421 177663
422 313131
423 293410
424 443765
425 247442
426 465283
427 215631
428 404495
429 316407
430 410781
431 186193
432 787710
433 187923
434 396207
435 351013
436 419685
437 210693
438 491673
439 193161
440 639065
441 370500
442 393267
443 196693
444 640185
445 248341
446 349671
447 290563
448 615315
449 202051
450 733460
451 229159
452 450905
453 298389
454 362299
455 323361
456 767715
457 209307
458 368697
459 371470
460 600005
461 212983
462 689871
463 214833
464 567021
465 400179
466 381661
467 218557
468 832650
469 259749
470 489769
471 322491
472 548855
473 251769
474 575211
475 307086
476 612465
477 372190
478 401527
479 229921
480 1074801
481 257481
482 408261
483 409773
484 567910
485 294717
486 696241
487 237657
488 586365
489 347529
490 618450
491 241573
492 783965
493 267397
494 488061
495 535990
496 646443
497 291441
498 634543
499 249501
500 710710
501 364741
502 442771
503 253513
504 1148550
505 319393
506 514843
507 404430
508 568995
509 259591
510 866047
511 307971
512 698027
513 461010
514 464149
515 332103
516 861315
517 300181
518 561393
519 391339
520 879315
521 271963
522 792610
523 274053
524 605255
525 597246
526 486031
527 304851
528 1125579
529 293090
530 621271
531 460330
532 760095
533 315309
534 729001
535 358267
536 706335
537 418873
538 508417
539 379050
540 1312850
541 293223
542 515991
543 428259
544 818769
545 371721
546 949221
547 299757
548 661745
549 491790
550 750386
551 331851
552 1114295
553 360297
554 539049
555 567021
556 681135
557 310807
558 903630
559 346419
560 1150317
561 530803
562 554701
563 317533
564 1026935
565 399373
566 562611
567 627627
568 792515
569 324331
570 1074801
571 326613
572 851865
573 476749
574 687477
575 445718
576 1403350
577 333507
578 623210
579 486759
580 945035
581 397461
582 865137
583 380779
584 837465
585 737490
586 603001
587 345157
588 1296750
589 378333
590 768397
591 507091
592 915957
593 352243
594 1126510
595 542469
596 782285
597 517413
598 708393
599 359401
600 1624090
601 361803
602 755307
603 592410
604 803355
605 503006
606 937573
607 369057
608 1016127
609 645411
610 820911
611 413031
612 1396850
613 376383
614 661899
615 694369
616 1175055
617 381307
618 974883
619 383781
620 1077405
621 669130
622 679231
623 456627
624 1548729
625 508431
626 687981
627 658749
628 868245
629 431949
630 1607970
631 398793
632 979755
633 581529
634 705649
635 503967
636 1302665
637 521550
638 810901
639 664690
640 1346485
641 411523
642 1051687
643 414093
644 1103235
645 762879
646 818769
647 419257
648 1706705
649 470953
650 1032486
651 735813
652 935655
653 427063
654 1091181
655 536083
656 1121673
657 702390
658 900543
659 434941
660 1875965
661 437583
662 769251
663 730353
664 1080815
665 673227
666 1280370
667 481663
668 981995
669 649389
670 988869
671 503139
672 1976247
673 453603
674 797349
675 975260
676 1088850
677 459007
678 1172353
679 541899
680 1475135
681 672841
682 924483
683 467173
684 1733550
685 586117
686 980350
687 684723
688 1232343
689 523929
690 1560013
691 478173
692 1053605
693 985530
694 845299
695 603291
696 1755065
697 528961
698 855057
699 708799
700 1607970
701 492103
702 1550010
703 536067
704 1435735
705 909571
706 874741
707 587271
708 1611155
709 503391
710 1109521
711 821730
712 1241705
713 549129
714 1592409
715 754509
716 1127735
717 745693
718 904687
719 517681
720 2623530
721 610641
722 965454
723 758199
724 1153005
725 702026
726 1476566
727 529257
728 1616805
729 896260
730 1172451
731 581151
732 1721265
733 538023
734 945399
735 1148550
736 1474851
737 606081
738 1567930
739 546861
740 1526595
741 906399
742 1142337
743 552793
744 2000895
745 692881
746 976521
747 906490
748 1429085
749 658749
750 1847846
751 564753
752 1469307
753 822289
754 1115751
755 711543
756 2413950
757 573807
758 1008147
759 956137
760 1830705
761 579883
762 1479387
763 683487
764 1283555
765 1237210
766 1029511
767 648003
768 2265263
769 592131
770 1645077
771 861991
772 1310505
773 598303
774 1722630
775 800358
776 1473585
777 1042587
778 1061977
779 656463
780 2581215
781 680029
782 1188397
783 1053910
784 1855350
785 769017
786 1573663
787 620157
788 1365245
789 902629
790 1371657
791 734331
792 2679950
793 692289
794 1106049
795 1153789
796 1393035
797 636007
798 1976247
799 692899
800 2149602
801 1041430
802 1128421
803 718599
804 2073435
805 977151
806 1272033
807 944203
808 1596965
809 655291
810 2389387
811 658533
812 1737645
813 958269
814 1309917
815 828723
816 2598141
817 721233
818 1173837
819 1356030
820 1869455
821 674863
822 1720537
823 678153
824 1660515
825 1393574
826 1412859
827 684757
828 2516150
829 688071
830 1513141
831 1001091
832 1975485
833 874950
834 1770951
835 869767
836 1773555
837 1201530
838 1231867
839 704761
840 3560505
841 733382
842 1243641
843 1030159
844 1565655
845 964410
846 2053870
847 924882
848 1863813
849 1044849
850 1732094
851 778071
852 2326415
853 728463
854 1509417
855 1535430
856 1791335
857 735307
858 2214849
859 738741
860 2053905
861 1276743
862 1303351
863 745633
864 3227070
865 933193
866 1315461
867 1157390
868 1981035
869 840693
870 2457091
871 833931
872 1858605
873 1235910
874 1474851
875 1157442
876 2458365
877 770007
878 1352127
879 1119859
880 2684073
881 777043
882 2593500
883 780573
884 1966335
885 1427023
886 1376851
887 787657
888 2835105
889 926649
890 1738387
891 1464463
892 1748355
893 859917
894 2033941
895 998851
896 2475795
897 1315587
898 1414357
899 864903
900 3667300
901 878941
902 1604113
903 1402713
904 1996865
905 1021233
906 2088723
907 823557
908 1811495
909 1339390
910 2263527
911 830833
912 3224403
913 927409
914 1465149
915 1524549
916 1843485
917 985701
918 2600290
919 845481
920 2657165
921 1229241
922 1490881
923 935679
924 3449355
925 1134042
926 1503831
927 1392690
928 2322957
929 863971
930 2801253
931 1085850
932 1908305
933 1261429
934 1529899
935 1265761
936 3687450
937 878907
938 1818243
939 1277679
940 2448845
941 886423
942 2257437
943 952819
944 2305191
945 2138070
946 1762383
947 897757
948 2876055
949 988749
950 2149602
951 1310491
952 2712345
953 909163
954 2605330
955 1136863
956 2007635
957 1505959
958 1609447
959 1077699
960 4350385
961 955266
962 1802367
963 1502410
964 2041305
965 1160733
966 2868411
967 936057
968 2515030
969 1520571
970 2063019
971 943813
972 3481205
973 1109277
974 1663599
975 1917474
976 2462733
977 955507
978 2432703
979 1065463
980 3092250
981 1558830
982 1691011
983 967273
984 3471845
985 1209217
986 1871779
987 1672437
988 2440305
989 1046829
990 3751930
991 983073
992 2648331
993 1428609
994 2040087
995 1233831
996 3172715
997 995007
998 1746507
999 1702470
1000 3147430