5000 49
104 788 876 176 444 692 608 220 856 180 764 444 520 152 736 968 880 876 696 168 164 676 804 64 240 548 740 500 620 568 196 372 756 928 968 556 852 448 272 720 436 912 248 364 668 744 548 888 416 680 436 236 804 660 944 568 216 252 400 900 96 264 912 372 56 976 148 824 936 956 784 396 624 380 636 236 708 868 920 180 300 396 796 192 956 380 412 184 440 488 724 296 828 788 764 664 864 876 524 564 248 804 784 872 476 868 748 868 708 664 752 444 876 420 512 112 704 68 248 964 776 840 920 408 204 128 580 828 936 716 652 724 936 584 628 408 144 640 128 500 828 276 60 172 776 776 304 460 468 144 840 72 932 452 236 884 848 696 308 448 424 688 412 540 296 600 168 244 188 916 92 736 888 168 964 132 972 532 668 596 164 420 144 240 828 280 760 468 516 520 492 980 708 544 96 276 616 72 60 424 800 596 468 108 672 240 656 704 272 280 652 432 116 1000 504 704 552 336 700 484 916 956 648 328 580 112 212 972 596 608 24 208 792 712 288 884 544 796 112 624 136 936 436 112 348 816 468 844 924 360 692 140 64 404 852 764 488 756 360 64 604 220 84 532 344 244 488 848 712 692 300 768 248 288 364 396 792 528 296 248 324 308 164 404 960 988 424 608 296 604 64 548 520 736 76 296 84 384 844 752 616 844 296 820 80 916 380 252 660 980 848 484 680 884 308 236 612 128 744 560 192 628 824 352 556 516 68 172 400 520 984 396 864 692 956 536 616 868 76 804 344 704 752 220 684 792 924 92 60 928 148 700 540 476 512 360 500 104 480 68 292 952 132 116 192 356 972 456 136 580 292 320 912 452 84 768 952 88 148 536 244 820 212 120 220 508 180 896 636 748 168 888 684 776 872 288 880 132 972 236 832 492 152 716 516 216 144 396 344 436 616 400 212 164 684 552 420 404 920 344 216 752 1000 448 856 676 440 76 876 152 568 444 472 856 64 940 500 908 312 300 412 460 892 248 748 868 304 584 760 56 248 600 828 592 996 828 352 572 772 428 376 340 376 384 604 320 560 664 416 744 896 772 532 852 216 112 596 880 948 304 132 844 764 620 888 292 684 796 924 488 588 604 836 472 620 60 300 436 812 396 816 148 448 200 932 784 728 532 460 348 736 488 884 712 880 664 464 168 128 536 780 972 444 480 776 932 676 936 856 580 184 148 372 524 692 120 720 528 784 968 960 580 596 240 668 628 428 68 472 232 332 508 900 508 120 872 80 112 956 408 64 956 656 676 876 432 304 528 160 424 900 792 444 892 104 776 448 744 424 716 200 900 288 220 540 836 184 752 460 500 136 100 784 664 988 292 756 320 68 964 772 528 108 592 104 456 424 248 116 644 656 132 564 624 464 828 156 156 372 688 680 960 256 236 112 768 448 160 208 92 108 608 772 220 176 424 808 468 552 728 620 244 696 392 572 652 556 380 904 576 740 852 648 316 396 332 492 576 756 736 484 748 316 596 60 132 392 272 816 248 600 968 72 532 696 780 460 396 144 152 464 776 292 636 240 708 516 184 420 872 296 696 460 228 908 76 200 336 192 108 472 200 84 348 68 444 196 84 580 308 136 512 72 200 488 184 956 560 540 328 464 300 468 824 608 308 360 924 332 364 92 684 248 712 852 624 932 496 76 400 544 808 304 856 412 504 432 896 192 612 724 660 916 220 64 984 880 644 240 76 176 988 572 772 912 596 336 720 704 328 860 992 260 588 780 324 136 300 520 648 428 308 528 1000 364 588 992 444 820 772 284 740 988 240 408 704 140 928 964 576 680 592 428 648 544 796 728 224 688 548 348 816 152 776 664 368 964 228 296 268 736 660 584 584 324 368 816 556 168 684 132 376 384 160 544 712 124 648 372 904 604 416 188 292 208 840 420 856 140 684 848 540 700 924 876 756 532 696 604 416 536 776 260 260 656 140 684 92 224 856 416 536 904 544 960 956 568 116 80 236 160 180 716 108 132 820 92 312 952 144 636 628 228 728 372 1000 304 232 212 720 940 280 796 428 88 832 864 744 244 708 764 828 836 504 904 656 316 580 112 112 292 604 720 168 872 164 592 124 168 496 632 248 988 628 120 860 380 932 940 80 620 796 400 768 344 380 716 596 660 940 384 736 780 104 592 804 92 488 260 176 872 744 736 600 612 956 348 108 72 712 60 912 116 460 496 176 752 576 552 708 348 912 436 840 168 116 540 464 732 688 84 76 420 536 324 288 440 684 780 924 824 876 400 156 852 232 728 416 548 596 252 500 124 128 336 176 860 560 720 364 720 256 904 972 124 764 172 604 188 388 416 832 468 488 836 832 672 876 412 848 668 532 196 756 712 816 372 268 500 740 832 508 192 632 308 860 888 404 356 840 516 968 624 472 380 444 476 132 780 736 692 672 76 844 404 328 892 964 844 956 600 372 260 672 836 828 868 984 232 740 332 396 680 808 212 700 532 740 344 960 516 584 604 208 252 692 992 228 384 660 160 792 324 552 468 344 552 120 596 292 84 124 108 256 104 560 236 756 80 324 268 472 968 432 292 724 756 560 792 140 456 232 324 160 912 460 412 72 380 488 372 288 716 380 168 484 620 472 588 820 672 628 816 904 996 244 676 308 336 852 980 468 696 124 912 432 112 584 332 240 724 704 732 952 656 756 212 300 888 92 244 660 908 88 492 836 88 564 340 492 892 692 1000 88 300 348 208 756 200 140 308 508 980 896 452 336 208 304 168 484 596 548 524 596 300 600 1000 528 236 400 792 400 888 324 92 180 136 708 652 484 856 200 212 288 768 636 860 16 476 972 744 696 992 592 420 380 76 828 488 476 516 116 720 852 412 376 116 896 612 188 584 464 228 664 112 416 228 956 732 448 520 912 824 208 832 64 236 552 612 680 292 788 608 824 680 464 108 488 264 300 268 584 856 448 936 160 736 520 608 868 968 912 896 176 396 420 624 948 96 828 320 464 444 280 428 244 736 460 124 608 520 304 152 400 196 836 480 532 828 60 864 252 816 908 888 976 964 484 196 392 644 256 88 692 956 596 388 972 332 644 220 904 152 764 320 504 136 952 324 500 516 252 736 612 268 96 204 356 124 584 776 516 972 316 784 240 164 412 780 640 728 872 920 452 724 120 312 676 592 988 152 312 464 356 572 808 480 992 780 600 812 360 420 80 192 396 584 852 936 888 652 488 988 780 100 208 196 928 848 304 308 144 852 336 636 708 384 248 624 296 392 284 100 496 800 912 664 148 916 856 684 824 964 728 728 940 408 124 876 492 896 100 244 812 840 356 660 352 380 724 296 992 392 296 456 872 656 940 372 548 464 380 240 84 76 708 412 528 384 808 80 772 860 232 140 252 284 504 72 396 544 632 772 560 100 740 368 464 880 960 116 196 740 348 424 528 156 452 628 624 816 972 924 492 940 648 236 160 712 724 328 452 584 540 908 92 380 392 204 504 112 64 196 420 376 388 652 940 432 356 676 492 564 512 308 968 628 220 916 472 88 484 788 208 776 212 816 432 288 400 828 548 448 692 872 384 828 880 928 868 524 132 172 60 336 852 896 428 516 476 956 60 696 664 640 388 696 924 980 800 156 848 380 824 600 364 704 924 208 448 976 324 312 464 648 664 136 236 224 576 424 796 496 900 960 264 300 416 412 148 620 640 584 884 592 236 700 240 356 220 516 1000 796 380 956 524 988 228 636 320 876 364 392 104 424 352 172 252 820 940 108 536 600 596 80 336 136 904 556 240 60 940 340 616 984 880 1000 948 908 900 984 824 976 732 812 548 88 172 164 596 812 928 656 124 148 448 124 392 636 108 272 112 524 976 408 652 64 492 660 172 524 164 116 548 944 404 424 200 228 320 560 544 992 820 424 520 980 404 476 436 928 964 536 284 836 264 480 876 976 800 192 592 736 768 864 924 156 644 176 944 340 452 728 136 952 504 848 592 424 128 320 760 752 356 916 724 124 316 992 344 644 492 552 996 288 480 324 592 56 980 288 456 116 440 960 624 528 528 388 916 112 624 280 984 860 512 712 236 908 176 360 588 644 272 648 596 280 864 156 572 728 960 516 848 908 564 672 688 980 272 180 200 832 80 648 916 588 700 560 944 708 832 464 340 352 480 972 484 352 280 532 68 116 900 848 912 936 980 712 576 544 136 892 736 772 144 216 892 384 260 880 972 184 380 504 592 300 56 192 660 296 800 868 476 608 872 608 816 832 368 124 768 312 952 92 100 240 448 104 808 964 748 436 724 988 492 832 972 368 172 416 652 852 916 176 692 164 736 316 916 668 208 728 760 436 68 668 260 324 940 424 916 104 560 136 968 268 860 664 572 224 120 80 172 936 56 448 768 576 168 696 648 284 432 472 440 656 368 280 768 272 952 464 344 688 332 920 576 692 408 240 568 152 640 164 812 704 468 568 472 976 300 876 92 832 176 332 248 488 372 220 460 784 156 948 664 572 888 524 772 224 132 532 636 568 384 428 596 168 940 840 836 480 196 292 312 924 588 720 536 288 192 548 464 332 196 896 572 532 132 180 60 308 708 704 624 232 876 996 284 88 976 60 488 164 60 212 800 652 616 940 724 960 204 544 376 996 624 616 336 520 660 420 404 256 244 908 368 800 760 308 196 92 620 344 480 212 448 964 752 348 880 56 988 580 208 940 268 880 804 144 732 768 392 384 348 436 772 428 296 432 352 544 376 836 960 296 64 748 644 648 952 804 316 732 448 424 924 332 204 460 480 416 416 836 752 160 452 392 496 448 504 240 88 308 796 380 416 996 780 700 504 840 952 700 276 788 564 508 284 440 704 448 412 132 60 468 588 820 392 844 948 352 980 328 484 464 768 240 832 468 624 176 864 288 848 396 832 456 372 588 888 464 884 68 168 376 796 440 140 124 756 872 148 352 136 784 496 708 296 924 792 340 528 212 220 176 388 380 104 852 924 880 848 900 864 788 180 132 172 956 676 376 416 184 928 1000 828 900 224 760 432 208 712 364 464 72 248 928 184 332 400 652 432 856 948 340 296 384 512 340 844 372 432 136 276 200 204 672 84 1000 800 144 352 536 660 820 396 916 80 836 748 260 408 456 936 888 848 568 540 632 984 324 72 584 612 596 788 432 936 240 632 436 728 116 740 852 64 668 840 252 376 440 68 472 884 952 724 104 548 740 588 804 700 156 108 380 520 752 516 444 168 912 872 468 400 148 336 400 684 172 368 992 816 172 796 156 588 724 880 200 440 484 876 508 84 400 996 492 104 748 692 936 668 412 868 688 148 988 284 464 188 772 448 864 736 496 784 888 996 688 64 756 992 200 124 260 392 564 316 484 492 372 732 412 484 384 588 284 776 244 676 860 232 260 704 376 744 340 880 460 344 944 608 304 140 596 156 916 548 444 576 976 440 608 220 632 420 76 412 956 828 252 824 144 488 360 752 280 360 636 996 500 240 304 460 72 936 112 716 740 280 552 456 520 580 188 608 556 308 628 904 592 828 532 744 888 964 784 768 192 416 544 140 424 276 576 516 652 336 772 672 816 464 412 776 256 72 168 60 984 300 348 504 764 404 192 320 88 696 712 128 224 568 980 736 60 560 116 428 792 200 484 456 240 208 240 616 744 108 120 288 96 456 148 568 580 312 464 160 660 572 564 616 512 240 560 332 600 316 716 980 784 116 576 868 968 960 584 688 132 580 136 716 76 72 724 716 416 460 520 472 100 376 184 76 684 916 584 192 208 708 584 456 172 868 220 264 380 348 88 536 460 112 360 836 448 236 344 304 980 444 512 360 992 692 228 92 212 932 120 568 708 476 304 1000 560 96 628 532 500 304 192 428 276 176 344 372 772 544 372 484 376 780 372 912 984 448 116 160 376 116 708 504 844 276 872 384 284 76 788 276 180 364 560 156 572 840 300 664 380 928 332 352 372 596 860 116 840 640 460 732 724 852 624 468 728 800 140 996 320 692 904 848 464 184 500 944 716 136 708 692 844 860 980 204 780 308 64 832 180 772 360 600 636 512 524 804 540 680 696 204 812 112 872 80 812 364 956 500 112 204 288 292 496 76 188 448 792 440 276 360 544 456 236 888 500 572 588 340 888 852 164 876 884 132 96 984 432 732 420 740 388 124 356 948 496 608 888 240 460 732 836 96 576 716 248 552 740 140 424 960 284 440 84 500 540 352 852 116 192 840 784 764 420 784 508 664 580 716 380 444 416 72 656 304 880 664 496 828 608 312 180 272 72 144 200 812 304 108 556 940 136 400 712 528 152 448 864 148 624 916 732 88 436 896 496 276 604 696 712 748 868 220 180 152 368 784 564 764 308 676 300 652 572 144 176 856 96 636 132 492 180 988 252 988 340 256 708 104 88 468 648 776 604 156 112 184 476 840 616 988 708 120 304 920 84 984 528 360 488 640 800 580 148 860 580 904 360 148 356 564 604 168 416 284 92 828 176 832 380 844 756 716 876 592 588 936 76 796 316 132 156 436 620 668 276 560 152 372 636 908 208 116 964 164 284 688 588 708 752 340 928 960 676 28 404 588 156 804 800 984 612 120 124 132 84 928 332 492 388 864 580 96 488 500 508 88 396 476 404 944 132 812 712 628 672 448 580 352 60 536 892 208 60 904 964 404 800 92 564 268 572 184 960 68 784 272 204 688 524 760 740 940 160 768 960 708 536 312 408 744 208 196 388 616 220 484 128 532 860 88 468 176 304 420 520 172 148 952 560 304 756 524 360 764 372 704 852 952 752 356 944 112 848 576 108 416 524 664 328 884 660 888 728 764 176 420 800 124 460 964 128 600 504 844 120 148 520 788 852 876 616 476 292 748 200 312 816 312 624 764 436 960 264 124 912 976 408 892 432 508 508 448 744 368 792 680 644 612 56 920 288 568 160 652 880 884 464 336 972 444 184 768 856 796 116 100 212 120 888 500 952 580 376 972 116 352 100 252 632 772 600 452 544 848 380 740 1000 924 828 268 392 240 264 900 748 664 652 896 892 616 668 508 108 908 756 800 624 132 312 240 632 456 492 236 728 248 844 64 332 700 868 624 168 680 796 784 516 612 864 984 480 744 204 812 708 804 876 748 880 580 980 340 244 892 952 540 72 240 500 984 384 400 76 960 420 660 412 196 996 836 532 852 540 80 680 124 192 260 452 920 916 564 228 932 788 592 460 580 200 564 824 800 388 736 476 80 304 364 568 288 180 520 324 140 736 208 64 636 684 884 60 184 704 776 192 832 916 856 164 372 156 772 628 448 496 648 656 752 484 552 680 780 476 844 184 628 916 976 452 988 124 80 300 804 384 248 172 356 884 940 412 944 440 260 928 468 672 504 772 284 712 260 272 648 476 244 900 536 692 652 772 672 292 68 548 300 468 396 380 316 708 676 496 608 256 692 636 668 516 212 636 148 280 920 900 564 232 448 192 92 900 624 212 444 876 872 980 592 616 292 720 640 964 764 368 680 560 916 532 76 376 560 916 792 964 488 492 160 628 928 336 332 624 388 108 688 692 172 660 412 272 472 948 524 360 700 364 588 164 160 908 428 464 696 876 968 280 64 212 900 576 728 848 796 144 104 736 448 540 608 308 808 740 252 72 392 604 908 480 496 588 88 760 292 848 764 164 940 956 432 680 560 84 800 740 776 448 876 268 208 400 76 460 220 304 760 776 264 272 144 752 464 376 388 448 776 752 784 212 820 188 688 312 128 892 524 424 312 376 732 996 440 364 420 900 332 360 320 740 432 364 316 136 24 912 440 640 676 712 680 456 56 492 356 824 548 668 688 300 756 708 864 232 820 724 1000 592 340 628 560 240 636 696 768 904 528 656 736 932 320 932 520 188 188 636 308 240 388 548 676 348 680 744 808 276 680 1000 276 768 380 516 104 280 500 840 500 96 560 900 212 804 916 412 352 424 844 912 976 160 228 268 180 184 512 452 768 104 260 800 992 704 180 308 480 248 756 356 932 404 452 640 944 776 956 584 576 748 688 852 964 432 896 564 504 848 720 208 292 844 956 248 324 56 764 544 912 616 680 648 348 644 284 988 616 888 164 684 64 496 384 372 132 396 540 792 496 444 480 676 832 288 256 624 712 340 336 908 792 964 556 116 384 292 648 992 656 468 828 460 112 964 588 524 252 616 544 152 56 148 924 396 684 520 788 828 968 464 796 788 796 304 336 1000 796 568 980 672 236 908 508 244 252 820 128 844 336 792 668 212 200 852 996 644 600 960 268 468 640 336 228 892 436 328 356 460 96 952 788 792 540 92 636 244 528 604 964 724 212 940 508 640 596 112 56 444 920 384 960 480 260 556 912 412 532 308 312 768 88 556 504 152 128 564 824 504 708 688 480 824 804 56 940 268 128 504 976 536 580 264 140 976 512 508 368 620 796 352 916 872 704 164 604 80 172 544 396 892 252 700 284 808 784 304 744 388 648 328 532 288 756 192 368 816 256 152 504 364 992 792 568 168 968 616 472 504 608 972 660 872 660 880 480 952 136 388 620 848 364 596 336 320 836 436 92 836 736 264 492 880 860 232 628 796 992 376 884 748 312 184 208 572 124 308 684 332 808 856 260 180 928 920 928 948 508 212 972 864 832 828 432 140 908 572 336 56 184 716 568 656 672 864 264 404 996 788 248 204 356 56 56 596 120 160 308 396 812 908 624 740 268 104 684 260 488 600 920 360 620 344 828 264 780 964 296 720 540 116 684 536 416 608 720 324 260 452 680 708 792 240 76 344 816 164 856 524 160 556 812 224 384 980 428 224 884 416 896 368 68 844 264 236 844 448 952 944 452 636 272 268 508 200 72 684 580 400 872 504 404 996 564 356 312 800 120 104 388 764 344 548 672 584 976 452 944 684 624 604 108 196 944 172 800 296 632 368 240 452 672 852 348 788 792 456 296 724 296 996 848 376 304 72 868 544 764 652 168 96 944 56 484 436 608 244 164 960 456 364 660 172 988 692 308 184 600 236 460 560 216 780 488 728 540 980 832 920 476 736 356 96 440 992 552 312 552 804 812 568 332 160 676 404 304 668 368 952 744 996 752 944 796 284 584 804 628 856 516 292 368 80 380 216 252 904 576 740 164 372 768 784 968 612 168 236 380 716 204 728 404 556 680 420 228 84 764 544 660 992 788 216 232 840 292 392 256 756 580 980 96 564 908 168 428 988 880 864 292 172 944 716 104 84 500 588 752 732 232 748 796 632 864 608 280 216 172 336 148 480 804 892 596 636 352 864 596 600 544 564 456 852 384 804 608 792 916 716 704 172 684 780 56 664 760 144 64 864 200 360 256 992 404 88 940 588 836 512 56 56 808 824 96 244 536 120 840 720 360 188 788 908 656 332 876 96 896 68 608 780 604 436 800 908 456 752 828 296 788 384 596 60 892 272 520 848 256 172 676 280 56 632 520 476 392 520 108 324 776 408 796 736 452 128 856 748 296 136 692 588 56 904 848 848 100 228 588 456 696 352 208 940 228 316 672 840 932 372 560 676 180 272 724 848 396 576 492 108 652 816 552 352 884 240 948 948 96 188 704 828 220 64 916 816 916 928 452 432 580 196 692 328 1000 212 960 436 836 784 164 404 456 452 468 560 856 88 424 148 796 440 128 200 640 836 680 156 92 128 264 960 616 160 64 804 392 928 1000 572 884 140 368 840 200 392 704 556 368 988 112 56 148 416 544 416 212 936 596 868 828 752 280 452 268 596 584 732 140 320 152 400 544 624 284 384 404 236 648 324 208 892 896 656 444 400 980 484 72 108 392 960 996 120 444 600 272 756 776 56 932 152 908 248 260 572 148 224 384 956 136 796 892 572 508 144 824 464 520 396 420 108 984 996 316 252 856 392 580 780 72 820 864 632 448 840 804 148 600 460 368 332 384 160 700 80 536 712 792 192 984 608 920 172 464 228 828 64 140 404 64 496 544 784 716 672 556 880 276 560 280 744 720 792 128 384 608 100 120 552 280 192 304 568 476 612 992 92 424 752 628 432 468 116 788 156 808 120 388 748 264 760 416 240 204 100 172 748 524 764 628 336 272 628 856 328 1000 880 612 312 592 424 396 872 632 488 904 860 656 556 528 516 208 420 80 616 368 672 400 236 460 964 964 124 664 196 68 856 368 340 208 560 684 796 860 616 604 368 660 396 452 824 420 500 320 492 784 788 980 456 148 416 784 588 464 560 676 668 532 760 312 692 368 268 316 940 832 944 596 408 272 572 360 636 412 292 936 552 556 652 632 972 328 712 84 952 296 196 464 68 660 128 192 688 152 412 792 840 276 784 592 852 100 560 400 188 656 508 368 724 596 208 444 488 120 416 372 136 164 612 788 700 916 260 844 100 588 1000 516 320 212 952 916 332 748 748 216 900 728 764 312 328 152 584 864 980 304 552 960 488 244 160 752 888 856 636 140 768 500 648 348 880 960 380 740 176 524 220 588 728 600 212 340 912 836 80 804 608 644 424 164 432 716 412 128 736 900 548 704 392 524 804 468 476 740 492 208 884 416 620 808 488 436 168 900 64 972 900 468 264 408 548 216 516 376 84 288 824 312 412 328 736 172 572 628 524 196 344 696 876 256 884 544 68 704 156 592 444 172 376 348 236 404 276 328 916 168 820 72 396 516 460 976 592 704 748 168 900 444 756 524 768 744 880 776 212 660 580 216 216 320 764 564 60 216 760 572 972 936 164 388 568 740 836 584 940 472 704 480 592 204 912 548 168 696 96 416 152 500 468 120 112 368 132 200 256 392 804 840 988 692 756 280 672 184 136 224 844 392 508 852 684 668 284 284 328 352 236 564 352 440 684 428 904 548 640 660 72 88 440 384 928 348 852 776 316 1000 568 984 972 528 560 484 224 404 228 116 820 772 804 616 864 160 740 520 704 64 304 404 680 252 1000 700 684 304 756 572 364 968 72 196 508 288 672 460 568 552 212 236 600 428 368 736 368 172 996 452 624 424 988 448 692 880 960 480 916 688 412 152 284 852 520 428 800 912 980 528 416 548 948 636 664 704 512 688 616 436 576 236 520 792 260 884 176 860 152 740 708 488 152 936 188 164 564 876 412 852 432 780 932 864 892 848 264 292 148 644 652 924 604 56 500 716 892 192 924 676 996 288 64 436 816 388 476 992 408 844 828 948 692 104 240 604 184 952 972 116 172 132 284 328 720 456 480 764 416 740 428 500 724 128 748 88 260 376 732 820 680 364 708 304 24 704 836 72 764 856 776 516 936 452 412 404 704 80 116 592 596 308 548 956 248 364
