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