1000 1000
987 524 561 738 496 511 452 285 451 591 422 838 880 524 658 599 752 676 880 750 492 173 17 993 295 71 316 548 308 48 992 919 961 815 819 284 370 317 11 807 945 161 779 663 412 483 688 4 863 595 508 25 428 371 67 587 88 122 493 50 96 915 963 497 651 85 436 25 466 500 626 75 861 336 9 805 40 244 352 851 703 713 12 42 957 228 497 514 179 14 82 114 958 203 579 577 602 518 356 930 838 82 953 918 896 451 760 817 763 230 339 342 774 783 934 668 679 530 523 461 536 732 716 572 360 482 705 527 741 362 187 222 704 769 696 811 290 212 880 810 278 315 686 475 590 83 556 485 195 436 408 453 439 930 995 511 461 231 325 588 236 465 345 686 512 783 214 864 593 386 488 617 672 354 556 962 279 263 356 405 496 929 74 225 713 258 791 812 814 378 542 176 871 43 213 825 564 30 988 365 439 341 442 397 265 115 996 388 743 801 390 365 270 603 559 850 493 266 944 610 970 603 814 42 903 72 912 704 166 629 851 12 467 509 100 31 537 654 637 280 664 11 612 21 134 569 256 343 227 572 798 66 337 266 483 419 739 200 66 410 13 380 520 602 165 691 255 191 361 403 768 735 337 36 548 124 630 155 909 593 140 623 432 131 787 175 478 874 28 835 35 288 730 603 534 345 30 749 275 108 608 83 725 329 67 619 160 147 233 833 918 896 70 698 431 14 889 658 383 152 728 521 915 706 636 530 620 393 405 148 959 967 7 324 804 973 469 570 678 585 340 131 34 955 332 679 347 947 370 956 365 405 881 867 73 823 979 377 321 2 179 417 381 47 284 975 116 524 471 64 71 495 281 721 362 347 851 277 236 953 351 755 482 656 303 79 847 55 167 808 534 835 782 450 347 117 793 869 127 709 546 573 810 421 311 491 894 823 101 804 426 544 718 497 676 569 657 431 539 844 305 471 347 964 192 440 402 968 582 516 187 665 12 937 569 466 150 313 974 544 329 100 444 793 217 836 940 522 79 793 494 420 424 694 128 334 233 180 826 649 393 181 769 168 432 828 826 454 143 275 298 5 632 677 555 28 288 573 690 456 857 407 791 271 253 790 437 833 967 597 170 535 900 41 465 169 211 982 494 538 97 146 986 415 880 39 832 600 65 565 462 30 519 271 944 910 678 517 881 452 844 610 188 956 935 23 987 956 303 735 989 126 749 676 973 621 260 130 8 886 614 275 144 2 674 291 39 104 749 852 725 360 783 581 670 333 256 502 398 298 203 256 767 113 761 835 316 344 729 887 94 518 158 222 207 308 242 666 365 950 978 988 122 364 89 93 841 812 89 304 115 299 487 79 715 724 959 269 959 944 865 380 137 455 618 840 548 525 149 964 946 32 35 331 805 681 537 170 733 329 282 468 210 470 508 269 763 439 631 612 966 492 19 746 80 377 841 8 647 868 709 49 310 189 58 971 865 398 287 364 578 843 681 250 107 268 929 27 269 225 455 942 984 397 551 258 212 989 603 358 104 963 705 921 721 822 807 979 813 12 508 827 111 339 760 122 582 253 726 615 402 610 577 93 319 474 206 178 717 323 377 202 406 71 770 876 946 818 272 642 208 195 678 543 806 57 686 772 66 392 188 363 298 147 300 40 857 716 735 212 355 362 257 68 395 635 846 810 722 858 839 466 803 722 824 328 637 564 556 568 41 525 146 501 60 412 857 47 143 986 434 55 317 651 342 700 261 964 424 219 825 414 819 634 398 82 815 598 317 380 928 862 945 973 744 255 66 468 175 753 537 325 448 74 837 525 349 58 85 13 765 127 463 213 757 546 681 330 301 601 294 586 220 222 499 856 903 520 658 940 110 320 823 877 695 167 345 41 232 318 299 140 751 230 884 239 588 122 995 467 705 649 519 286 848 664 847 5 622 720 221 707 679 355 368 729 410 61 778 351 334 337 223 881 269 753 535 501 640 658 270 668 299 191 914 607 619 189 716 893 981 647 571 210 824 914 893 610 366 620 344 790 927 721 528 877 751 518 673 335 241 970 784 446 900 201 437 934 37 707 492 863 68 925 28 841 955 38 6 351 653 4 682 558 980 759 7 712 478 183 451 796 112 786 706 489 867 25 481 211 534 883 373 668 284 242 951 87 872 213 203 497 670 973 242 576 388 956 573 305 273 2 362 965 668 122 92 660 872 605 246 101 703 598 448 235 108 654 901 924 838 376 564 695 362 351 438 788 975 30 255 57 968 297 569 713 486 371 813 927 
0 183 114
2 2409
0 365 65
0 175 85
1 57 447
2 160405
2 1493
0 440 185
1 271 986
1 68 443
2 1709
2 316336
1 865 971
2 37004
0 862 23
1 233 417
1 549 934
1 6 624
2 192610
0 867 57
1 163 496
2 141358
1 812 829
2 124918
1 588 697
2 8001
2 5297
2 144758
1 658 987
1 695 888
0 748 44
2 5181
2 273642
2 321248
2 3967
2 6245
1 102 589
0 527 220
2 77
2 8720
1 472 714
0 120 86
1 443 561
0 250 112
2 5497
1 140 986
0 521 226
2 2410
0 609 88
1 606 938
1 61 930
1 33 973
2 6850
1 675 949
1 869 956
1 438 608
1 182 210
1 489 908
2 1966
2 7730
1 413 947
0 607 161
2 41951
2 7872
2 3606
2 138028
1 14 391
0 312 107
1 153 492
1 51 659
2 57954
0 767 185
2 3606
2 38093
1 208 910
2 476370
1 140 545
1 289 644
2 8618
2 5653
1 574 901
2 1940
0 667 86
0 660 30
0 983 64
0 988 106
0 808 108
0 53 98
1 701 800
2 178352
2 5856
1 405 684
0 166 95
2 291245
2 7752
2 115799
2 778
0 792 12
2 1366
1 207 788
2 307406
0 252 172
2 998
1 303 412
0 395 115
0 960 167
0 450 207
2 6488
1 177 977
0 771 190
2 2419
1 650 848
0 620 155
2 357634
0 519 213
0 973 224
0 730 207
1 188 215
1 81 502
1 257 317
2 6715
1 729 756
2 4079
1 387 537
1 86 664
1 327 376
0 140 55
1 218 951
1 117 607
2 161
1 245 619
1 621 687
2 50963
2 7426
1 267 968
1 738 822
0 501 216
1 92 635
1 297 914
0 351 128
1 320 929
2 6131
0 196 158
0 998 105
1 363 524
0 754 66
1 430 883
2 323860
0 221 160
0 869 9
2 3021
0 687 135
0 26 82
2 391
0 666 229
2 354459
0 244 67
1 563 699
1 654 792
0 815 71
2 3585
2 436293
0 239 57
0 889 24
1 613 806
1 108 825
2 134765
0 829 213
1 67 91
1 16 646
2 241416
0 141 199
2 340122
1 3 239
0 752 158
2 141144
1 277 431
1 579 921
2 119799
2 177801
0 289 40
2 1016
2 9852
2 226457
0 694 214
1 529 798
1 292 613
1 938 938
0 241 8
2 4250
2 2810
0 19 79
2 15641
1 837 897
0 856 131
2 428064
1 642 790
2 5983
1 540 852
0 303 8
2 364631
1 396 450
2 3479
1 436 610
1 289 361
1 90 913
1 20 608
1 619 980
2 38352
2 9761
1 165 556
1 166 501
2 448451
0 434 214
1 146 558
1 136 202
2 96796
1 559 966
0 682 235
1 703 755
1 44 660
1 566 975
2 248492
2 262510
0 610 116
0 871 137
0 216 233
1 128 528
0 76 160
1 455 490
0 201 110
1 86 359
0 185 32
1 505 812
1 213 937
0 742 213
1 169 297
2 419081
1 396 460
0 825 4
1 216 700
2 489029
0 766 60
2 190983
0 107 97
1 25 902
2 331086
2 294170
0 110 214
1 457 705
2 324893
0 584 240
2 365819
1 542 853
1 239 585
1 132 487
0 612 151
1 171 408
1 231 918
1 301 938
0 826 239
2 183571
2 1702
0 522 77
1 81 719
0 279 250
1 450 569
1 312 873
0 123 132
1 454 742
1 184 620
0 393 177
2 287487
1 720 968
0 745 166
2 2268
0 680 204
2 43574
2 7736
2 131693
2 54
0 161 24
2 2113
2 170081
0 102 106
1 145 347
1 324 698
1 814 986
1 308 592
1 129 474
0 372 203
2 312739
0 869 120
2 443904
0 823 45
1 730 921
0 589 133
0 474 104
0 385 4
2 71281
1 316 431
2 4811
1 495 496
1 111 299
2 2766
2 4788
1 704 720
0 743 226
1 275 478
0 743 14
1 523 697
0 613 93
0 196 178
0 436 153
2 2052
1 468 690
2 8709
1 655 872
2 1525
1 362 479
2 1942
1 106 814
2 9499
2 431430
0 84 79
2 238435
0 199 195
2 9158
1 36 188
0 564 103
1 47 551
1 500 614
2 9252
1 278 545
0 40 225
0 256 175
2 6994
2 7015
0 193 195
2 285
0 493 142
1 501 619
0 165 141
2 29607
1 567 918
2 402795
2 77840
1 316 622
0 571 199
2 83441
0 400 80
0 770 28
1 118 404
0 716 10
1 395 829
0 61 218
0 344 219
1 78 128
2 382590
2 5463
1 271 275
2 447510
1 955 977
2 331967
0 921 179
0 950 179
0 516 50
1 15 527
2 8114
2 188750
0 630 81
0 944 118
1 88 548
2 464087
0 51 125
2 93144
2 467267
1 519 847
0 586 243
2 3642
0 815 192
0 415 180
1 99 650
1 131 968
1 773 917
2 411030
2 2477
2 353740
1 55 425
1 4 807
0 96 139
2 28768
0 446 29
0 360 195
2 7263
2 105023
1 153 357
1 466 529
2 82519
1 85 760
0 393 84
2 189445
2 7240
0 968 31
2 210308
1 219 403
1 8 131
0 731 195
2 8956
1 262 728
0 285 83
0 790 218
2 184625
1 519 953
1 212 734
1 498 627
0 306 204
2 433874
0 323 155
1 685 724
0 934 125
1 9 861
2 152222
2 2586
2 193084
2 300488
1 773 973
1 128 898
0 92 150
2 3052
2 24402
2 283332
2 7747
1 60 890
0 912 237
2 238370
2 87314
0 900 20
0 53 192
2 1181
0 434 112
2 204369
0 297 116
1 675 996
1 299 499
0 329 91
2 29857
0 312 207
2 255386
2 2999
0 140 102
2 2221
1 7 722
1 14 371
1 618 772
1 221 264
0 350 64
1 875 994
1 319 476
1 104 925
1 183 486
1 728 864
2 1805
0 306 171
0 318 20
1 25 383
2 264614
1 296 769
2 4114
0 589 176
0 105 83
0 315 225
2 311296
1 367 855
0 350 215
1 83 373
0 123 155
2 325017
0 837 25
0 284 203
2 186
1 294 766
1 389 436
2 366686
0 686 140
1 291 901
0 577 123
0 81 202
2 7841
0 133 94
0 942 109
1 330 790
1 234 730
0 676 195
0 237 12
2 333170
0 879 235
1 564 860
0 695 40
1 537 609
2 541
1 505 583
2 7901
0 844 127
2 425369
0 417 244
1 184 197
0 902 102
0 81 35
1 247 310
0 416 38
0 327 113
0 470 19
0 253 53
1 10 316
1 518 744
0 72 110
0 981 84
2 9483
1 479 499
0 84 181
1 742 934
1 906 906
1 570 716
2 287480
1 650 846
0 70 132
1 277 677
1 563 650
0 877 222
0 690 126
2 9329
0 289 196
0 874 54
1 24 449
2 3036
2 147573
2 4800
2 138159
1 826 837
0 894 26
0 395 42
2 384536
0 392 212
0 618 94
2 102943
2 220000
0 497 120
2 213557
1 83 297
2 1024
0 497 102
2 69628
0 95 84
0 731 45
0 530 26
1 162 625
0 955 234
0 18 126
2 181334
1 295 910
0 12 172
1 345 798
2 116851
2 167646
0 917 139
1 738 782
2 426396
1 50 897
1 601 953
0 933 111
0 479 130
1 253 522
1 742 817
1 450 623
0 399 66
1 396 836
0 9 199
1 360 454
1 350 691
2 417499
2 359978
1 227 887
0 375 46
0 680 70
0 976 117
1 165 265
0 766 201
1 661 877
2 1664
0 595 34
2 435
0 619 107
2 4554
1 508 939
1 170 691
2 4692
1 273 794
2 288375
2 491841
2 317685
2 5572
2 26457
1 4 935
2 400531
0 761 137
0 739 179
0 236 248
2 261
1 229 688
1 444 852
2 4282
1 164 769
1 234 408
0 606 154
2 84767
1 287 807
0 713 187
1 76 815
1 546 741
1 562 636
0 566 126
1 172 951
0 339 113
1 186 263
0 123 94
0 544 168
1 799 804
2 8552
0 47 133
1 365 973
2 409901
2 31844
0 296 176
2 9641
1 12 895
0 164 206
2 494046
1 324 815
0 64 102
2 214466
0 963 54
2 35882
1 412 565
1 529 801
1 327 523
0 2 160
2 9481
0 18 249
0 57 167
1 474 756
2 505376
1 359 437
2 67365
1 453 880
2 518943
0 771 163
1 219 931
2 3298
1 114 325
2 5099
1 613 914
2 6
1 468 855
2 303918
1 462 539
0 468 37
1 229 920
1 188 846
0 690 202
1 284 962
2 11851
0 346 180
2 831
0 242 250
2 6283
2 2851
1 206 514
2 4109
0 669 126
0 889 139
2 6102
2 8333
2 27687
0 784 220
1 555 876
0 117 69
1 509 702
2 7325
2 6046
1 124 421
0 658 145
2 172669
0 660 11
0 760 233
0 398 93
2 4279
2 6052
2 7671
2 433571
1 764 969
2 4318
2 403186
0 314 138
1 6 522
2 7614
2 435797
0 907 166
1 321 673
1 14 623
0 13 2
1 468 700
1 106 131
0 385 53
0 587 211
2 66339
2 433975
1 227 307
2 13562
1 438 949
2 1641
1 337 684
2 355172
0 864 78
1 220 345
0 516 247
2 527012
0 577 46
1 318 353
1 316 476
1 751 810
0 538 47
0 862 34
1 404 759
0 34 98
0 737 132
2 377819
0 545 84
2 4806
1 44 460
0 308 216
2 5544
1 56 588
1 146 280
0 193 186
0 593 206
1 811 920
0 915 182
1 87 623
1 638 978
2 184492
0 696 93
1 585 878
2 399001
1 213 763
2 286404
0 135 197
2 98034
1 240 971
1 596 746
1 219 827
1 5 647
1 430 713
1 448 779
1 181 513
2 779
0 686 80
0 454 190
1 427 987
1 247 655
0 757 131
0 326 230
1 627 938
2 3620
0 760 125
1 136 586
1 202 964
2 6552
1 351 367
1 624 788
0 642 249
0 770 135
2 1424
2 7888
1 804 861
2 9416
2 16549
1 50 642
0 662 9
1 302 855
2 468653
1 320 713
2 7149
0 209 239
2 30625
0 193 149
2 404281
2 136696
0 938 97
2 529
2 324435
2 115756
2 344614
0 434 122
1 30 639
1 482 680
1 304 531
2 9741
0 271 197
1 448 737
1 222 921
2 1985
1 408 411
2 14244
0 296 176
1 108 572
2 526678
2 8926
2 7584
0 960 124
0 5 45
0 528 222
2 253929
2 7063
1 355 754
0 442 23
0 399 179
1 22 917
2 171965
0 736 69
1 611 638
2 203703
2 14099
2 1927
0 178 217
2 6526
1 188 303
0 40 209
0 772 17
2 30879
0 727 227
0 464 79
1 255 782
1 215 987
0 32 242
0 269 159
0 761 50
0 998 109
2 145185
0 374 33
2 26979
0 387 115
2 144264
1 387 970
0 747 124
2 1132
1 360 509
0 294 104
2 9602
1 447 837
0 873 128
0 481 174
1 106 346
0 898 55
1 729 998
2 218321
1 496 983
1 157 901
2 41174
0 612 79
1 995 1000
2 2518
1 115 766
1 199 831
2 4806
1 49 413
2 6376
2 110897
1 391 842
2 161543
2 9887
1 327 542
2 191
0 595 168
0 637 123
0 846 23
0 346 144
1 804 817
0 232 190
2 221516
2 423923
1 47 896
1 708 806
2 1007
2 467481
2 421690
2 3155
1 292 463
0 187 197
2 1903
0 126 150
0 365 123
1 301 656
0 501 164
1 415 891
0 478 178
2 2216
1 325 671
1 72 992
1 434 584
2 189085
1 709 840
0 793 120
0 341 127
1 120 577
1 200 208
2 387837
0 571 212
1 315 537
1 733 952
2 9751
2 514749
0 888 164
1 397 807
0 129 40
1 690 832
0 242 46
0 781 164
1 303 542
0 933 4
1 438 649
1 670 742
1 132 293
2 6782
1 547 744
0 882 18
2 191173
1 125 681
0 553 91
1 567 868
2 496530
0 997 145
1 181 254
1 396 969
1 451 503
0 834 10
2 40160
1 66 475
1 327 559
1 384 394
2 533090
0 93 74
2 145334
0 274 109
0 629 248
1 122 833
2 357879
2 7302
2 2253
2 280349
0 811 75
1 638 819
1 176 358
1 593 680
2 499893
1 20 710
1 172 232
2 7134
2 8432
1 243 267
2 395146
2 249037
1 587 831
0 59 211
2 382391
1 685 836
1 946 976
1 68 294
0 10 89
2 516092
0 729 211
0 271 65
0 131 80
1 275 289
2 95418
2 1787
2 8056
0 822 162
0 397 68
1 177 184
0 67 241
2 8466
1 557 962
0 960 141
0 865 25
0 700 16
1 78 694
2 370340
0 139 196
1 861 971