1 0
2 0
3 0
4 1
5 0
6 1
7 0
8 2
9 1
10 1
11 0
12 4
13 0
14 1
15 1
16 5
17 0
18 4
19 0
20 8
21 1
22 1
23 0
24 14
25 1
26 1
27 3
28 16
29 0
30 10
31 0
32 22
33 1
34 1
35 1
36 41
37 0
38 1
39 1
40 45
41 0
42 18
43 0
44 57
45 9
46 1
47 0
48 94
49 1
50 8
51 1
52 102
53 0
54 38
55 1
56 138
57 1
58 1
59 0
60 221
61 0
62 1
63 17
64 231
65 1
66 59
67 0
68 298
69 1
70 22
71 0
72 468
73 0
74 1
75 9
76 491
77 1
78 104
79 0
80 644
81 30
82 1
83 0
84 922
85 1
86 1
87 1
88 1005
89 0
90 245
91 1
92 1256
93 1
94 1
95 1
96 1784
97 0
98 16
99 58
100 1996
101 0
102 300
103 0
104 2439
105 23
106 1
107 0
108 3431
109 0
110 63
111 1
112 3735
113 0
114 493
115 1
116 4566
117 103
118 1
119 1
120 6269
121 1
122 1
123 1
124 6843
125 7
126 946
127 0
128 8349
129 1
130 108
131 0
132 11099
133 1
134 1
135 203
136 12313
137 0
138 1258
139 0
140 15040
141 1
142 1
143 1
144 19684
145 1
146 1
147 17
148 21638
149 0
150 2169
151 0
152 26018
153 299
154 71
155 1
156 33530
157 0
158 1
159 1
160 37547
161 1
162 3365
163 0
164 44584
165 64
166 1
167 0
168 56837
169 1
170 304
171 492
172 63262
173 0
174 4568
175 21
176 75192
177 1
178 1
179 0
180 95557
181 0
182 116
183 1
184 105561
185 1
186 6845
187 1
188 124755
189 819
190 497
191 0
192 155391
193 0
194 1
195 109
196 173648
197 0
198 11123
199 0
200 204828
201 1
202 1
203 1
204 251966
205 1
206 1
207 1257
208 281606
209 1
210 15988
211 0
212 329932
213 1
214 1
215 1
216 405245
217 1
218 1
219 1
220 452259
221 1
222 21640
223 0
224 527032
225 2154
226 1
227 0
228 639689
229 0
230 1262
231 72
232 715223
233 0
234 33554
235 1
236 831821
237 1
238 312
239 0
240 1004868
241 0
242 57
243 3010
244 1121506
245 21
246 44586
247 1
248 1300159
249 1
250 1993
251 0
252 1561874
253 1
254 1
255 305
256 1741630
257 0
258 63264
259 1
260 2014930
261 4567
262 1
263 0
264 2397773
265 1
266 505
267 1
268 2679690
269 0
270 97889
271 0
272 3087752
273 117
274 1
275 62
276 3658658
277 0
278 1
279 6844
280 4092150
281 0
282 124757
283 0
284 4697206
285 498
286 157
287 1
288 5546599
289 1
290 4572
291 1
292 6185690
293 0
294 174429
295 1
296 7089503
297 10170
298 1
299 1
300 8326573
301 1
302 1
303 1
304 9289108
305 1
306 251990
307 0
308 10620931
309 1
310 6849
311 0
312 12411397
313 0
314 1
315 15854
316 13848651
317 0
318 329934
319 1
320 15804594
321 1
322 1270
323 1
324 18405064
325 107
326 1
327 1
328 20506258
329 1
330 462517
331 0
332 23338470
333 21639
334 1
335 1
336 27068455
337 0
338 102
339 1
340 30179407
341 1
342 639713
343 15
344 34262965
345 1263
346 1
347 0
348 39598338
349 0
350 16988
351 31212
352 44108318
353 0
354 831823
355 1
356 49995926
357 313
358 1
359 0
360 57650754
361 1
362 1
363 58
364 64114816
365 1
366 1121508
367 0
368 72533824
369 44585
370 21644
371 1
372 83303501
373 0
374 353
375 2127
376 92669723
377 1
378 1561208
379 0
380 104676981
381 1
382 1
383 0
384 119847585
385 76
386 1
387 63263
388 133230931
389 0
390 2046185
391 1
392 150201736
393 1
394 1
395 1
396 171617835
397 0
398 1
399 506
400 190606212
401 0
402 2679692
403 1
404 214481127
405 92114
406 4580
407 1
408 244340884
409 0
410 44590
411 1
412 271248951
413 1
414 3658682
415 1
416 304801574
417 1
418 546
419 0
420 346460670
421 0
422 1
423 124756
424 384276339
425 303
426 4697208
427 1
428 431149390
429 158
430 63268
431 0
432 489023348
433 0
434 6857
435 4573
436 541946241
437 1
438 6185692
439 0
440 607238518
441 174329
442 398
443 0
444 686971076
445 1
446 1
447 1
448 761010274
449 0
450 8415230
451 1
452 851376629
453 1
454 1
455 121
456 961313821
457 0
458 1
459 239970
460 1064248791
461 0
462 10631797
463 0
464 1188908265
465 6850
466 1
467 0
468 1340090618
469 1
470 124761
471 1
472 1482074146
473 1
474 13848653
475 496
476 1653680800
477 329933
478 1
479 0
480 1860262305
481 1
482 1
483 1271
484 2056149000
485 1
486 18387472
487 0
488 2291320915
489 1
490 188547
491 0
492 2572799923
493 1
494 591
495 461557
496 2841940517
497 1
498 23338472
499 0
500 3163330205
501 1
502 1
503 0
504 3546255290
505 1
506 1311
507 103
508 3913864296
509 0
510 30419224
511 1
512 4351078600
513 614181
514 1
515 1
516 4869471581
517 1
518 21652
519 1
520 5371595152
521 0
522 39598362
523 0
524 5964539505
525 17778
526 1
527 1
528 6664865513
529 1
530 329938
531 831822
532 7346655159
533 1
534 49995928
535 1
536 8149040698
537 1
538 1
539 70
540 9093742294
541 0
542 1
543 1
544 10015581889
545 1
546 64146679
547 0
548 11097645017
549 1121507
550 454207
551 1
552 12364770160
553 1
554 1
555 21645
556 13610949896
557 0
558 83303525
559 1
560 15066438143
561 354
562 1
563 0
564 16763234184
565 1
566 1
567 1508479
568 18440293323
569 0
570 105290816
571 0
572 20390986040
573 1
574 44598
575 1261
576 22660354757
577 0
578 298
579 1
580 24909568701
581 1
582 133230933
583 1
584 27517052602
585 2043836
586 1
587 0
588 30538752497
589 1
590 831827
591 1
592 33549419514
593 0
594 171546579
595 317
596 37027355201
597 1
598 1356
599 0
600 41044598849
601 0
602 63276
603 2679691
604 45060624583
605 62
606 214481129
607 0
608 49686288630
609 4581
610 1121512
611 1
612 55014437595
613 0
614 1
615 44591
616 60356751050
617 0
618 271248953
619 0
620 66494475448
621 3554372
622 1
623 1
624 73536765225
625 1958
626 1
627 547
628 80630964770
629 1
630 348050427
631 0
632 88751778805
633 1
634 1
635 1
636 98046674970
637 115
638 4621
639 4697207
640 107439892747
641 0
642 431149392
643 0
644 118159172852
645 63269
646 787
647 0
648 130402396132
649 1
650 2016878
651 6858
652 142798995931
653 0
654 541946243
655 1
656 156919475312
657 6185691
658 124769
659 0
660 172998905360
661 0
662 1
663 399
664 189334822582
665 510
666 686971100
667 1
668 207890420103
669 1
670 2679696
671 1
672 228965361691
673 0
674 1
675 8210202
676 250438927453
677 0
678 851376631
679 1
680 274771693154
681 1
682 6898
683 0
684 302345502045
685 1
686 173645
687 1
688 330495499630
689 1
690 1067802052
691 0
692 362326859896
693 10630752
694 1
695 1
696 398313267858
697 1
698 1
699 1
700 435161977313
701 0
702 1339814382
703 1
704 476715865408
705 124762
706 1
707 1
708 523597073528
709 0
710 4697212
711 13848652
712 571701605658
713 1
714 1653921225
715 162
716 625846753121
717 1
718 1
719 0
720 686822051964
721 1
722 491
723 1
724 749474411782
725 4571
726 2056159091
727 0
728 819877191073
729 18004327
730 6185696
731 1
732 898975016944
733 0
734 1
735 189337
736 980462880639
737 1
738 2572799947
739 0
740 1071830842237
741 592
742 329946
743 0
744 1174273332797
745 1
746 1
747 23338471
748 1280011055229
749 1
750 3171451319
751 0
752 1398341745588
753 1
754 4666
755 1
756 1530818207620
757 0
758 1
759 1312
760 1667736667768
761 0
762 3913864298
763 1
764 1820701100653
765 30407197
766 1
767 1
768 1991626193333
769 0
770 11087044
771 1
772 2168627105470
773 0
774 4869471605
775 6848
776 2366022741848
777 21653
778 1
779 1
780 2586221899643
781 1
782 1552
783 38887700
784 2814571510905
785 1
786 5964539507
787 0
788 3068829878531
789 1
790 13848657
791 1
792 3352028543008
793 1
794 1
795 329939
796 3646072432126
797 0
798 7347269602
799 1
800 3973014796644
801 49995927
802 1
803 1
804 4336510019663
805 1275
806 6943
807 1
808 4714566886086
809 0
810 9110765222
811 0
812 5134205998750
813 1
814 21693
815 1
816 5600100813130
817 1
818 1
819 64144245
820 6085274320969
821 0
822 11097645019
823 0
824 6622987708043
825 463481
826 831835
827 0
828 7219202922635
829 0
830 23338476
831 1
832 7840656234255
833 311
834 13610949898
835 1
836 8528581328848
837 82010204
838 1
839 0
840 9290192373920
841 1
842 1
843 1
844 10085065885768
845 107
846 16763234208
847 70
848 10963707205276
849 1
850 30181355
851 1
852 11935116832403
853 0
854 1121520
855 105265277
856 12950095925898
857 0
858 20391027213
859 0
860 14070579899025
861 44599
862 1
863 0
864 15307804477174
865 1
866 1
867 299
868 16601599401350
869 1
870 24948451980
871 1
872 18028182516674
873 133230932
874 1745
875 16834
876 19601367028065
877 0
878 1
879 1
880 21248323079204
881 0
882 30540253905
883 0
884 23061871188199
885 831828
886 1
887 0
888 25059416090188
889 1
890 49995932
891 169232855
892 27152408925616
893 1
894 37027355203
895 1
896 29454551675031
897 1357
898 1
899 1
900 31987483695687
901 1
902 44639
903 63277
904 34643126322522
905 1
906 45060624585
907 0
908 37561133582571
909 214481128
910 66142166
911 0
912 40767740628382
913 1
914 1
915 1121513
916 44132934884256
917 1
918 55011365087
919 0
920 47826312174768
921 1
922 1
923 1
924 51880400334631
925 21643
926 1
927 271248952
928 56138148671156
929 0
930 66576478954
931 504
932 60806135438330
933 1
934 1
935 358
936 65925110620653
937 0
938 2679704
939 1
940 71304278059922
941 0
942 80630964772
943 1
944 77195892663529
945 343922327
946 63317
947 0
948 83649841856033
949 1
950 104678929
951 1
952 90436842747839
953 0
954 98046674994
955 1
956 97862933703586
957 4622
958 1
959 1
960 105989788777917
961 1
962 21738
963 431149391
964 114540884553039
965 1
966 118162726721
967 0
968 123888443151449
969 788
970 133230937
971 0
972 134108638361887
973 1
974 1
975 2045760
976 144867692496462
977 0
978 142798995933
979 1
980 156618566629687
981 541946242
982 1
983 0
984 169453621360674
985 1
986 4862
987 124770
988 182973889881888
989 1
990 173168139552
991 0
992 197726516681881
993 1
994 4697220
995 1
996 213826231304745
997 0
998 1
999 679903230
1000 230793744766458