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