1000 2
0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 1 2 0 2 0 3 0 0 2 0 0 0 0 0 0 0 2 0 0 0 0 0 1 3 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 0 0 0 3 0 0 1 0 0 0 0 0 0 0 0 0 1 2 0 0 3 2 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 2 0 0 0 2 0 0 0 0 0 0 2 0 0 1 0 0 0 2 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 2 0 0 0 3 0 0 1 1 0 0 0 0 2 0 0 0 0 0 2 0 1 0 0 0 0 0 0 1 0 0 0 2 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 1 0 1 0 0 1 2 0 0 2 2 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 1 0 0 2 0 0 0 0 0 0 2 0 0 0 0 0 1 0 1 0 3 2 0 0 0 0 0 0 0 2 0 0 0 1 0 2 0 0 1 0 0 0 2 0 0 0 2 0 0 0 0 0 0 0 0 1 2 0 0 1 0 0 0 0 0 2 0 0 0 0 0 0 2 0 0 0 2 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 1 0 0 1 2 0 0 0 2 1 0 0 2 0 0 0 2 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 3 0 1 0 2 1 0 2 0 1 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 0 1 0 0 0 2 0 0 0 0 0 0 0 1 2 0 0 0 2 0 2 1 1 0 1 0 2 0 0 0 0 1 0 0 0 2 0 0 3 0 0 0 0 0 0 2 0 0 2 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 2 0 0 1 0 0 0 0 0 0 0 0 2 2 0 2 0 1 0 0 0 0 0 0 0 0 0 0 2 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 2 2 1 0 0 0 0 2 2 0 1 0 0 0 0 1 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 3 0 0 2 0 2 0 1 0 0 2 0 0 1 0 0 0 0 0 0 0 2 2 0 2 1 0 0 1 0 0 1 0 1 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 1 0 1 3 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 2 2 1 0 0 0 0 2 0 0 2 1 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 2 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 2 0 0 1 0 0 0 1 0 0 0 0 2 0 1 0 0 0 0 0 0 1 0 1 0 0 0 2 0 0 0 0 0 0 0 0 0 1 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 2 0 1 0 0 2 0 0 0 2 0 1 0 0 0 0 2 0
1 332
1 587
2 252
2 413
3 169
4 392
5 376
6 656
7 824
8 538
8 902
9 657
9 941
10 819
11 794
12 38
12 396
12 563
13 176
13 644
14 709
15 144
15 153
16 61
16 167
16 514
16 777
17 296
18 122
19 136
19 149
20 535
20 725
21 361
21 596
22 447
23 280
24 616
25 444
25 546
26 28
26 609
26 977
27 138
29 672
30 248
30 307
30 651
30 763
31 289
32 356
32 783
33 452
33 785
33 963
34 889
35 449
36 164
37 92
37 424
39 267
39 491
39 806
40 223
40 239
40 364
41 855
42 597
43 550
43 746
44 892
45 924
46 115
46 482
46 659
47 531
48 597
48 808
49 517
50 284
51 534
52 204
53 833
54 111
54 171
54 884
55 120
55 267
55 454
56 369
56 434
57 518
58 229
59 325
60 481
60 519
61 583
61 706
61 748
62 316
63 96
63 243
63 863
64 191
64 202
64 351
64 781
64 969
65 564
65 944
66 331
67 385
67 403
68 370
69 160
69 201
70 310
70 760
71 643
72 727
72 908
73 299
74 854
75 368
76 183
76 607
77 854
78 357
78 998
79 469
79 485
79 883
80 386
80 546
81 157
81 394
81 809
81 941
82 511
82 654
83 283
84 121
84 165
84 426
84 772
85 256
85 263
85 949
86 251
86 549
86 966
87 252
88 853
89 705
90 111
91 635
93 154
93 788
93 935
94 478
94 887
95 321
95 895
96 241
96 749
97 614
98 155
98 299
99 158
100 649
101 512
101 943
102 150
102 300
102 639
103 967
103 992
104 774
104 824
104 874
105 187
105 512
106 132
106 397
107 566
108 502
108 741
109 315
110 142
110 825
111 634
112 155
112 664
113 771
114 909
115 211
115 789
116 622
116 740
117 141
117 984
118 490
118 905
119 240
119 748
120 265
121 527
121 596
121 835
122 248
123 517
123 701
124 134
125 294
125 511
126 406
126 637
127 330
128 567
129 382
129 803
130 163
130 691
130 929
131 197
131 559
131 695
132 370
133 434
134 395
134 405
134 451
135 1000
136 752
136 937
137 658
138 211
138 581
139 150
139 838
140 762
141 209
141 737
141 893
142 757
143 612
143 904
144 839
145 851
146 956
147 249
147 284
148 753
149 201
149 801
149 819
150 973
151 360
151 950
152 226
154 580
155 582
156 275
158 545
158 793
159 300
159 609
159 864
160 723
161 376
161 457
161 545
162 282
162 345
162 686
163 387
163 488
163 801
164 528
164 648
165 974
166 387
168 218
169 179
170 544
170 620
171 270
171 441
172 204
172 657
173 240
174 623
174 692
174 809
175 436
177 342
177 518
177 866
178 471
178 692
178 930
179 761
180 645
181 334
182 201
182 736
184 349
184 377
184 576
184 788
185 749
186 530
187 759
188 487
189 949
190 353
190 875
191 248
191 442
191 653
192 212
192 402
193 224
193 392
193 493
194 385
195 328
196 401
196 614
196 968
198 636
198 982
199 557
200 629
201 846
202 380
203 241
203 322
203 628
204 640
204 882
205 329
205 582
205 635
205 765
206 232
206 791
207 347
207 707
207 902
208 438
208 599
208 767
210 325
210 463
211 758
213 933
214 629
215 298
215 880
216 626
216 670
217 252
217 567
218 249
218 716
219 474
219 868
220 839
220 895
221 820
222 277
222 908
223 753
223 875
224 530
225 382
225 515
226 941
227 492
227 818
228 670
229 279
229 830
230 900
231 768
232 440
232 627
233 531
234 607
235 946
236 970
237 254
237 742
237 994
238 562
239 621
239 700
242 887
243 331
244 996
245 588
246 621
246 696
247 895
249 856
250 275
250 359
251 856
253 837
255 286
255 525
255 544
255 961
257 888
258 506
259 791
260 269
261 341
261 565
262 319
264 948
265 898
266 381
266 879
267 435
268 558
268 710
268 1000
269 309
269 926
270 391
271 378
272 552
272 966
273 791
274 473
274 592
275 828
276 815
276 945
277 807
278 452
278 755
279 730
279 916
280 320
280 346
280 847
281 313
281 480
281 682
282 878
283 780
284 366
284 433
284 792
285 429
285 598
285 718
286 452
287 772
288 355
288 499
288 592
289 310
289 484
290 682
290 739
290 948
291 570
291 688
292 754
292 805
293 446
294 422
295 500
295 501
295 639
295 764
296 683
296 812
296 865
296 900
297 660
297 945
298 543
298 675
298 817
298 890
299 568
299 915
299 933
300 990
301 533
302 645
303 408
303 919
304 337
304 595
304 797
305 384
305 497
305 697
306 389
307 680
308 576
311 925
312 629
312 664
314 803
315 521
315 694
316 542
316 846
317 585
317 934
318 601
319 960
320 420
321 628
321 721
322 745
323 392
324 633
324 671
325 875
326 911
326 915
327 362
327 800
327 959
328 666
328 819
329 400
330 443
330 932
331 807
332 374
333 454
333 464
334 486
334 563
334 811
335 575
335 600
336 831
337 693
338 693
339 551
340 470
340 559
341 914
342 738
343 577
344 508
345 555
347 531
347 826
347 910
348 681
348 818
350 939
351 532
352 823
354 683
354 912
355 829
356 581
356 751
357 747
358 456
360 571
362 827
363 664
363 978
364 580
365 766
365 853
367 593
368 689
369 853
370 415
371 478
371 685
372 455
373 498
373 594
375 589
375 637
376 547
377 599
378 934
379 417
379 543
380 662
382 951
383 875
385 790
385 952
388 407
388 972
389 604
389 995
389 999
390 455
392 707
392 767
393 831
394 849
396 879
397 423
397 564
398 483
398 592
398 787
399 837
400 804
400 967
401 622
402 544
402 903
403 440
404 807
404 997
405 653
405 843
406 794
406 810
407 840
408 867
408 922
409 747
410 485
410 547
410 625
411 665
411 892
412 527
413 796
414 777
415 636
416 850
416 962
417 579
418 872
419 553
419 919
420 711
421 465
421 826
421 869
423 427
423 503
423 993
424 632
424 786
425 606
425 732
428 465
428 685
428 954
429 562
429 592
429 760
429 899
430 786
430 814
430 914
431 667
431 757
431 888
432 810
433 840
434 883
435 895
436 854
436 980
437 868
439 664
443 444
445 711
446 720
447 678
448 930
449 536
449 925
449 929
450 619
450 729
450 737
450 857
451 832
453 960
455 717
456 623
456 894
458 899
459 461
459 646
459 820
459 876
460 482
460 837
462 666
466 477
466 738
466 976
467 616
468 739
468 963
472 980
473 590
474 513
475 559
476 563
478 631
479 620
481 916
482 851
484 956
487 567
487 828
488 722
489 495
489 626
491 734
492 923
494 621
496 797
496 979
497 682
499 957
500 607
502 511
502 551
504 966
505 624
506 974
507 629
508 788
509 695
510 647
510 892
511 706
515 614
516 525
516 839
517 780
517 828
518 675
520 696
521 979
522 607
523 593
523 609
524 560
524 619
525 813
526 917
528 894
529 709
529 933
531 780
531 964
533 778
534 644
534 652
535 626
535 989
536 622
536 921
537 735
538 743
539 540
540 652
541 597
541 611
541 962
544 714
544 782
546 614
546 834
547 569
548 945
550 896
554 881
556 868
557 852
558 601
558 886
560 912
561 805
561 970
562 931
564 822
564 896
565 674
565 996
566 950
568 661
569 836
570 599
572 627
573 612
573 992
574 677
575 629
575 845
577 634
578 735
579 855
584 733
586 749
587 772
588 674
589 711
591 910
594 664
594 687
596 858
599 642
602 761
603 760
604 751
604 826
604 833
605 663
606 617
606 891
606 924
606 949
607 638
607 816
608 793
609 668
609 960
610 629
610 649
610 874
612 652
612 844
613 712
613 795
614 886
615 646
615 848
616 916
617 660
618 658
618 884
618 923
620 773
623 860
623 971
624 810
625 702
625 885
626 944
628 779
630 824
633 724
633 884
634 799
636 698
637 953
639 684
641 839
643 904
644 784
645 843
645 958
648 986
649 810
649 838
650 922
652 909
655 677
656 821
656 985
657 975
663 750
663 759
665 914
669 897
670 936
672 778
673 788
676 793
677 797
678 791
679 981
687 728
687 747
687 912
689 710
690 749
694 775
694 974
695 931
696 831
697 763
697 872
699 889
700 859
701 836
703 737
704 989
705 857
706 749
708 755
713 735
713 856
714 861
715 890
716 814
717 787
717 791
719 720
720 968
721 808
723 941
726 891
730 998
731 930
733 761
733 795
734 947
738 903
740 942
742 953
744 904
750 980
755 814
756 847
759 869
760 821
761 879
761 889
762 880
764 987
766 888
768 873
768 896
769 809
769 919
770 944
771 858
775 877
776 923
776 981
778 834
786 950
794 955
798 992
800 815
800 845
802 928
805 937
816 944
820 901
820 955
822 878
823 864
827 842
833 906
833 928
834 923
834 988
836 939
840 907
841 992
849 934
852 923
854 881
856 931
861 937
862 933
868 955
870 980
871 925
872 960
878 897
879 927
885 926
891 991
899 910
901 946
905 993
913 918
917 945
918 963
919 938
920 954
923 974
927 961
938 983
940 967
965 1000
