2
997 800 100000
98 90 90 84 82 75 74 71 63 60 60 54 48 45 40 38 35 30 29 20 21 13 8 4 4 8 16 25 31 41 47 50 61 64 71 77 86 96 103 108 117 120 130 137 143 152 155 166 173 179 185 191 202 197 192 189 186 182 179 176 168 167 164 160 156 151 148 144 136 134 134 130 123 120 115 113 106 102 110 115 127 134 138 145 149 159 169 172 182 186 197 203 211 216 222 228 235 242 248 257 265 268 275 287 293 298 297 295 290 288 282 275 273 271 267 260 256 252 251 247 243 238 235 229 230 224 220 218 214 209 200 208 217 221 233 241 248 250 260 264 276 278 287 291 304 310 314 324 331 337 342 347 359 364 369 379 383 394 398 399 391 387 387 381 380 373 368 369 361 361 351 348 343 342 335 336 328 324 322 321 316 310 309 300 313 318 324 328 336 346 354 358 369 371 382 387 395 403 407 412 423 429 439 442 451 460 467 470 481 483 489 498 498 493 488 483 479 479 471 466 465 463 457 457 453 449 442 436 436 431 425 420 422 418 410 406 405 407 418 424 434 438 444 450 462 467 472 482 486 492 503 508 516 525 526 536 543 548 556 566 573 577 587 591 598 600 594 590 588 578 574 575 569 566 559 555 556 549 547 545 539 534 528 530 526 516 514 510 506 502 508 519 525 532 535 547 552 559 566 570 580 585 597 602 609 616 623 627 637 641 647 660 663 668 680 683 689 697 696 690 687 683 681 679 675 668 667 659 660 651 647 649 640 639 635 632 625 625 621 618 613 609 605 607 617 625 634 638 644 650 658 666 672 680 686 697 703 709 718 720 728 737 740 748 754 762 773 776 787 790 802 797 794 788 785 778 780 772 768 769 763 757 752 751 748 740 738 736 733 724 725 721 715 712 710 703 710 717 723 729 737 743 753 756 766 770 782 784 792 803 809 815 819 831 833 844 851 856 867 870 875 884 894 900 900 895 890 885 879 874 874 869 869 861 856 853 847 848 839 836 835 832 828 822 819 815 814 804 805 812 815 824 828 841 847 854 858 865 871 878 884 894 901 911 915 921 927 937 940 953 957 965 972 976 986 989 999 997 995 991 988 982 975 974 968 967 961 959 956 948 947 944 938 932 933 930 920 920 913 920 920 930 933 932 938 944 947 948 956 959 961 967 968 974 975 982 988 991 995 997 999 989 986 976 972 965 957 953 940 937 927 921 915 911 901 894 884 878 871 865 858 854 847 841 828 824 815 812 805 804 814 815 819 822 828 832 835 836 839 848 847 853 856 861 869 869 874 874 879 885 890 895 900 900 894 884 875 870 867 856 851 844 833 831 819 815 809 803 792 784 782 770 766 756 753 743 737 729 723 717 710 703 710 712 715 721 725 724 733 736 738 740 748 751 752 757 763 769 768 772 780 778 785 788 794 797 802 790 787 776 773 762 754 748 740 737 728 720 718 709 703 697 686 680 672 666 658 650 644 638 634 625 617 607 605 609 613 618 621 625 625 632 635 639 640 649 647 651 660 659 667 668 675 679 681 683 687 690 696 697 689 683 680 668 663 660 647 641 637 627 623 616 609 602 597 585 580 570 566 559 552 547 535 532 525 519 508 502 506 510 514 516 526 530 528 534 539 545 547 549 556 555 559 566 569 575 574 578 588 590 594 600 598 591 587 577 573 566 556 548 543 536 526 525 516 508 503 492 486 482 472 467 462 450 444 438 434 424 418 407 405 406 410 418 422 420 425 431 436 436 442 449 453 457 457 463 465 466 471 479 479 483 488 493 498 498 489 483 481 470 467 460 451 442 439 429 423 412 407 403 395 387 382 371 369 358 354 346 336 328 324 318 313 300 309 310 316 321 322 324 328 336 335 342 343 348 351 361 361 369 368 373 380 381 387 387 391 399 398 394 383 379 369 364 359 347 342 337 331 324 314 310 304 291 287 278 276 264 260 250 248 241 233 221 217 208 200 209 214 218 220 224 230 229 235 238 243 247 251 252 256 260 267 271 273 275 282 288 290 295 297 298 293 287 275 268 265 257 248 242 235 228 222 216 211 203 197 186 182 172 169 159 149 145 138 134 127 115 110 102 106 113 115 120 123 130 134 134 136 144 148 151 156 160 164 167 168 176 179 182 186 189 192 197 202 191 185 179 173 166 155 152 143 137 130 120 117 108 103 96 86 77 71 64 61 50 47 41 31 25 16 8 4 4 8 13 21 20 29 30 35 38 40 45 48 54 60 60 63 71 74 75 82 84 90 90 98
