P13993 [HackerEarth] Most of the events were over and the participants were roaming about in the Nirma Campus when they reached the Nirma Lake. It is a Large lake and to get to the other side of the lake, yo
普及
题目描述

Most of the events were over and the participants were roaming about in the Nirma Campus when they reached the Nirma Lake. It is a Large lake and to get to the other side of the lake, you have to go around it. So, participants decide to construct plans for bridges on the lake. They identify points on each side of the lake on which Bridge end points can be made. The students then decide that a bridge can only be built between corresponding end points, i.e. a bridge starting from the ith end point on one side can only end on the ith end point on the other side, where the position of end points is seen in the order in which the points were identified. They just wants to make as many non-cutting bridges as possible, with the constraint in mind. Bridges "cut" if and only if they have exactly one common point that is not an end point.

Input:

The first line of the input contains test cases t. It is followed by 3*t lines, 3 for each test case. The first line of input for each test case contains the number of end points identified on each side, n. The second line contains x-coordinates of end points identified on the first side and similarly the third line contains the x-coordinates of corresponding end points identified on the other side. The end points are givenin the order in which they were identified.

Output:

You are required to output a single line for each test case. The line contains a single integer – the maximum number of bridges possible with the constraints explained above.

Constraints:

1 ≤ t ≤ 50

1 ≤ n ≤ 1000

-1000 ≤ x-coordinates ≤ 1000

SAMPLE INPUT
3
4
2 5 8 10
6 4 1 2
3
5 3 10
6 4 1
6
1 2 3 4 5 6
3 4 5 6 1 2

SAMPLE OUTPUT
2
2
4

输入格式

见题面

输出格式

见题面

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