P19614 [HackerEarth] Gitam is a priest in his village. He needs to pay his respects to k shrines which his all ancestors have visited and had asked their successors to pay the respect. But he hates walking s
普及-
题目描述

Gitam is a priest in his village. He needs to pay his respects to k shrines which his all ancestors have visited and had asked their successors to pay the respect. But he hates walking so he wants to minimize the distance he has to travel to pay his respects. As he is busy packing he asks you to help him. He has acquired a bunch of portal scrolls through which he can create portal networks. gateways can only be created at shrines , and after entering a portal a he can exit at any desired portal. You have to give the minimum distance Gitam has to travel. There are number of cities which don’t have shrines but that can be traveled through.
You will be given n the number of cities and out of which first k cities have shrines. There is road connecting two cities which will be defined by three integers a, b and c where a and b are the cities and c is the distance between the cities. You have to calculate the minimum distance that need to be walked for this pilgrimage given that there is no restriction on number of gateways that can be created but need to be created at shrines. After you have told him the distance he’ll decide whether it’s worth undertaking or not. You can assume that he starts from 1st city.

[Input]
First line contains integer t denoting number of test cases.
First line of every test case consists of 3 integers n, m and k denoting number of cities, number of roads and number of shrines respectively.
Next m lines of test case consists of 3 space separated integers a, b and c, where a and b are cities and c is the distance between them.

[Output]
For each test case print a single integer containing the minimum distance he need to walk for the pilgrimage.

[Constraints]
1 ≤ t ≤ 20
1 ≤ n ≤ 100
n-1 ≤ m ≤ (n*(n-1))/2
1 ≤ k ≤ n
1 ≤ a,b ≤ n
1 ≤ c ≤ 1000000

SAMPLE INPUT
1
5 10 3
1 2 10
1 3 5
1 4 10
1 5 80
2 3 9
2 4 1
2 5 20
3 4 100
3 5 2
4 5 20

SAMPLE OUTPUT
14

输入格式

见题面

输出格式

见题面

样例输入
20 49 81 42 1 2 733422 2 3 180800 3 4 914 4 5 418039 5 6 832414 6 7 316923 7 8 823330 8 9 97833 9 10 651324 10 11 382528 11 12 215352 12 13 711718 13 14 69063 14 15 82677 15 16 257954 16 17 384052 17 18 773470 18 19 602833 19 20 958647 20 21 114306 21 22 426686 22 23 215805 23 24 815975 24 25 819705 25 26 663245 26 27 425473 27 28 129596 28 29 363904 29 30 381519 30 31 838320 31 32 805507 32 33 740908 33 34 916099 34 35 218806 35 36 151850 36 37 460929 37 38 102621 38 39 923394 39 40 615533 40 41 934002 41 42 702267 42 43 486254 43 44 758559 44 45 353482 45 46 457556 46 47 244533 47 48 780709 48 49 345715 1 5 281845 3 5 642512 4 11 959292 1 7 989948 2 11 765783 44 47 241890 3 7 318269 24 33 332085 14 44 63040 13 21 572158 1 42 335271 28 33 852857 6 16 699207 11 19 726759 11 22 159184 12 16 950441 31 44 697485 16 37 28816 31 35 51671 3 25 132534 6 12 989068 11 46 728877 4 21 545185 1 8 476915 20 26 331870 19 39 36101 8 21 224691 27 39 863947 20 47 651892 12 20 944280 6 30 772207 35 39 931795 4 13 456917 39 67 8 1 2 939699 2 3 494999 3 4 528448 4 5 878817 5 6 814535 6 7 82887 7 8 730721 8 9 687515 9 10 998604 10 11 799916 11 12 839115 12 13 17729 13 14 189709 14 15 256219 15 16 513206 16 17 471357 17 18 320796 18 19 122033 19 20 193431 20 21 395847 21 22 558856 22 23 259208 23 24 840451 24 25 676873 25 26 253168 26 27 108095 27 28 537633 28 29 883326 29 30 797634 30 31 735802 31 32 985144 32 33 168732 33 34 66058 34 35 187349 35 36 623516 36 37 736511 37 38 32617 38 39 590912 3 19 975103 5 15 920140 4 11 789958 5 10 971714 3 7 259517 20 31 371417 1 33 550984 2 26 413054 1 6 253521 25 37 990095 10 20 910126 1 28 750356 5 31 577250 16 33 904690 13 29 505096 25 28 481751 10 12 377717 11 15 809943 16 22 7383 11 29 612121 17 32 739913 2 10 804530 16 23 872968 4 25 234022 7 26 934102 21 38 182599 15 38 971019 2 15 43845 8 28 293059 90 187 10 1 2 627422 2 3 970728 3 4 768842 4 5 419845 5 6 133708 6 7 744471 7 8 612109 8 9 304796 9 10 43438 10 11 58175 11 12 453743 12 13 260514 13 14 660795 14 15 824968 15 16 812516 16 17 394638 17 18 180803 18 19 737688 19 20 2292 20 21 914974 21 22 381582 22 23 826412 23 24 315837 24 25 747008 25 26 825654 26 27 944506 27 28 272770 28 29 214837 29 30 638074 30 31 539063 31 32 346239 32 33 866135 33 34 209594 34 35 951846 35 36 377910 36 37 845224 37 38 282497 38 39 716361 39 40 517465 40 41 414811 41 42 599070 42 43 661518 43 44 473237 44 45 896759 45 46 58091 46 47 356747 47 48 742570 48 49 59602 49 50 390204 50 51 938705 51 52 458719 52 53 939438 53 54 604515 54 55 952838 55 56 760531 56 57 646455 57 58 29478 58 59 153117 59 60 334080 60 61 784818 61 62 228856 62 63 50032 63 64 450393 64 65 397904 65 66 521588 66 67 759918 67 68 540815 68 69 101561 69 70 54923 70 71 107002 71 72 481055 72 73 894249 73 74 341474 74 75 351543 75 76 796771 76 77 610089 77 78 135063 78 79 174853 79 80 650435 80 81 14221 81 82 755358 82 83 124119 83 84 153806 84 85 997463 85 86 580195 86 87 267173 87 88 504352 88 89 640577 89 90 270300 62 68 74382 4 77 575544 13 70 706715 38 73 349692 1 3 61589 10 32 684423 14 24 882783 65 68 663395 15 25 96182 19 58 413201 45 77 352869 21 45 330533 52 66 593660 42 63 45195 4 39 850956 7 10 968793 75 77 82549 52 57 93352 27 86 378087 43 46 844034 20 30 46493 31 42 115962 22 49 971408 23 25 737984 3 65 353160 1 16 58327 17 73 697686 28 89 214324 18 58 742612 18 76 354130 20 23 708346 3 21 35110 16 67 782853 16 31 733344 1 9 93204 3 34 233376 2 59 312153 24 40 502909 39 44 802808 36 41 302707 29 48 526440 5 13 807182 33 51 88424 3 74 185219 10 50 363091 24 53 595788 8 65 896340 13 71 710772 46 56 759774 76 86 307429 52 68 995185 43 56 388228 12 14 566306 22 53 590946 22 35 775242 64 73 746434 12 19 325375 70 78 656171 34 88 195253 19 27 833320 3 44 467920 26 61 365369 16 30 370118 2 45 946628 18 59 543984 31 56 256649 5 16 665704 7 26 695309 10 17 273183 57 61 302897 11 52 171702 1 25 639419 1 6 414698 29 39 49872 12 16 510804 16 89 255050 27 63 514302 54 65 423033 9 11 185589 23 42 883920 2 10 982875 1 69 979556 14 17 856942 39 62 187225 11 17 116581 67 89 656011 14 53 483990 54 80 352213 32 68 819160 34 87 823738 54 61 190120 6 47 807784 1 30 587261 10 48 260813 6 23 779347 78 88 514555 7 28 9759 2 74 259629 9 23 5 1 2 279710 2 3 279867 3 4 741569 4 5 770423 5 6 66546 6 7 937437 7 8 185428 8 9 832199 2 5 380118 1 4 466222 5 7 664191 2 4 150268 4 6 671304 1 3 815841 4 7 770516 1 7 826635 5 8 314209 3 8 370042 3 5 207434 3 6 742275 2 8 677232 2 6 217719 6 8 68634 48 48 17 1 2 861971 2 3 696143 3 4 210963 4 5 915296 5 6 914141 6 7 407613 7 8 643927 8 9 356647 9 10 754263 10 11 719165 11 12 146554 12 13 331924 13 14 490520 14 15 710282 15 16 258580 16 17 880672 17 18 856099 18 19 482025 19 20 605150 20 21 629198 21 22 517707 22 23 736007 23 24 616759 24 25 116284 25 26 669317 26 27 242852 27 28 204427 28 29 38794 29 30 672032 30 31 892421 31 32 235562 32 33 169949 33 34 692769 34 35 267565 35 36 263910 36 37 167806 37 38 165337 38 39 602835 39 40 114013 40 41 814808 41 42 300966 42 43 293660 43 44 875105 44 45 311983 45 46 806824 46 47 471743 47 48 6840 13 28 171085 24 40 17 1 2 252034 2 3 810475 3 4 658242 4 5 758189 5 6 359321 6 7 941472 7 8 256306 8 9 214463 9 10 511765 10 11 327991 11 12 994056 12 13 288485 13 14 872807 14 15 392205 15 16 692414 16 17 143862 17 18 791918 18 19 113071 19 20 178459 20 21 45907 21 22 407333 22 23 252101 23 24 720632 9 22 14493 1 4 998107 6 9 962046 11 13 905941 10 23 720967 3 9 703192 2 19 452454 4 6 998001 1 12 92790 4 7 21141 5 7 376864 9 12 583424 14 17 808505 12 21 846108 11 15 129274 17 20 578559 12 22 56438 45 47 9 1 2 569953 2 3 71443 3 4 72761 4 5 42988 5 6 424588 6 7 947100 7 8 492849 8 9 643584 9 10 534746 10 11 453139 11 12 252348 12 13 859917 13 14 24930 14 15 937372 15 16 538117 16 17 748975 17 18 513793 18 19 611640 19 20 918509 20 21 829198 21 22 966202 22 23 95845 23 24 677515 24 25 465446 25 26 946947 26 27 369045 27 28 976854 28 29 588921 29 30 27583 30 31 456999 31 32 208077 32 33 249244 33 34 164711 34 35 669350 35 36 607753 36 37 493773 37 38 52240 38 39 911850 39 40 681623 40 41 481316 41 42 468817 42 43 56386 43 44 829187 44 45 431300 9 15 28589 4 6 820378 6 18 812861 97 178 43 1 2 999780 2 3 100366 3 4 837185 4 5 70870 5 6 181327 6 7 488848 7 8 522573 8 9 799163 9 10 916102 10 11 831815 11 12 256232 12 13 112151 13 14 707899 14 15 93482 15 16 768789 16 17 679461 17 18 725439 18 19 585260 19 20 878177 20 21 28702 21 22 297372 22 23 799418 23 24 779153 24 25 810848 25 26 339268 26 27 276828 27 28 280643 28 29 972806 29 30 560048 30 31 230257 31 32 804318 32 33 461379 33 34 834306 34 35 990752 35 36 983844 36 37 851735 37 38 124013 38 39 520516 39 40 429293 40 41 721442 41 42 349895 42 43 706087 43 44 499877 44 45 889328 45 46 301550 46 47 340211 47 48 671809 48 49 542309 49 50 650228 50 51 283524 51 52 748410 52 53 618622 53 54 21625 54 55 57301 55 56 829156 56 57 620260 57 58 501871 58 59 353853 59 60 590962 60 61 458553 61 62 424024 62 63 205398 63 64 28315 64 65 328699 65 66 33642 66 67 842240 67 68 415179 68 69 975475 69 70 96730 70 71 11625 71 72 484854 72 73 953662 73 74 471422 74 75 711125 75 76 33811 76 77 417375 77 78 396027 78 79 260452 79 80 40111 80 81 164283 81 82 489337 82 83 529560 83 84 974226 84 85 558341 85 86 252458 86 87 343214 87 88 427612 88 89 892229 89 90 507664 90 91 112922 91 92 568849 92 93 141282 93 94 295110 94 95 540583 95 96 830434 96 97 631327 28 71 18145 8 69 463650 23 52 529634 10 24 905533 32 57 408677 6 51 979127 36 82 839591 11 13 439745 39 56 72747 10 16 354189 47 49 50792 1 4 872792 23 50 319968 1 20 475274 37 70 759209 29 55 468339 23 31 514562 13 70 755153 49 52 124633 2 43 479214 45 61 38815 53 65 558234 21 29 746359 37 49 399522 17 38 959112 71 74 643455 2 13 720108 7 10 608720 16 25 85998 67 72 345116 4 13 757973 3 41 169295 57 70 336393 66 80 739326 88 92 672426 38 67 55723 3 43 950921 25 39 239861 17 29 502665 1 48 51423 31 51 290075 6 28 252727 57 65 467708 4 36 266554 3 21 561797 80 92 516388 32 48 261571 66 70 507369 27 63 210896 3 5 595370 9 79 274528 25 28 741725 8 24 263411 52 83 478336 2 32 779279 2 27 126371 10 52 629906 53 57 860969 8 31 326585 16 52 16276 70 94 227960 30 82 186263 21 39 667103 4 70 103801 27 87 903201 2 12 504015 1 7 879935 31 65 102188 23 53 685968 16 48 897723 9 56 749529 42 87 636467 2 4 6449 29 32 801853 9 26 825492 57 83 156178 13 31 833984 49 77 754811 12 56 996910 10 25 707511 9 52 536047 7 39 709332 15 73 9 1 2 711180 2 3 216348 3 4 895776 4 5 2198 5 6 615424 6 7 461546 7 8 463244 8 9 450903 9 10 663994 10 11 43749 11 12 492022 12 13 731793 13 14 391450 14 15 436658 4 10 746191 5 14 724878 9 13 823170 2 11 340667 5 8 106679 1 5 304571 2 7 128953 4 9 629282 5 10 403925 3 11 641245 1 9 286091 4 13 424747 1 3 943272 8 12 249876 2 10 714390 4 6 170659 8 11 754681 4 12 680115 9 14 10816 10 13 780335 4 7 989724 3 6 258580 1 7 301803 5 12 684561 6 12 212630 2 4 763478 6 11 614266 5 9 972203 10 12 803930 6 8 36560 7 13 383068 1 4 933604 7 9 210377 4 8 429099 3 9 950362 3 12 293861 5 7 906810 2 8 887500 3 5 787274 11 13 821658 7 11 235545 7 10 10133 1 8 956355 9 11 16815 3 7 114825 11 14 361242 2 12 829669 7 12 560981 2 5 979706 2 13 737194 1 6 648541 1 14 408790 10 14 982534 6 14 31278 6 10 751557 2 6 583623 1 12 799798 9 12 569393 4 11 370647 51 66 5 1 2 988874 2 3 107841 3 4 682151 4 5 939354 5 6 235541 6 7 824707 7 8 945395 8 9 320982 9 10 605896 10 11 149279 11 12 344083 12 13 804278 13 14 866647 14 15 679732 15 16 416647 16 17 244107 17 18 596308 18 19 965073 19 20 676578 20 21 140873 21 22 215730 22 23 907741 23 24 741502 24 25 997556 25 26 614660 26 27 342868 27 28 82995 28 29 167488 29 30 113274 30 31 366290 31 32 892962 32 33 412979 33 34 764940 34 35 764005 35 36 670278 36 37 229647 37 38 25143 38 39 227852 39 40 841514 40 41 327584 41 42 311985 42 43 26942 43 44 169422 44 45 92712 45 46 398225 46 47 284270 47 48 381861 48 49 445847 49 50 995573 50 51 861138 1 8 580158 1 20 208298 1 7 685614 23 29 616440 4 30 333049 34 39 55642 1 11 923004 9 40 354956 15 22 36249 7 17 537561 36 49 34201 26 36 36598 5 11 634555 22 48 437731 33 47 460192 5 9 740305 21 83 10 1 2 791020 2 3 358494 3 4 201197 4 5 552314 5 6 234562 6 7 614116 7 8 372598 8 9 382790 9 10 543639 10 11 976369 11 12 462432 12 13 636784 13 14 402535 14 15 125168 15 16 854512 16 17 166764 17 18 512717 18 19 132864 19 20 554100 20 21 461571 4 14 574281 3 13 349513 4 8 676499 1 12 376539 4 19 64599 3 6 868641 1 3 955205 8 11 458790 7 13 994150 2 8 10695 11 13 438020 1 5 238558 3 19 3321 2 4 780230 3 10 907604 9 16 697467 11 16 249978 13 20 49951 5 14 29147 7 14 985439 6 18 32341 9 18 224026 3 7 978856 10 12 78851 12 15 616905 7 19 512593 1 9 464125 12 16 630885 9 20 819652 3 16 417615 3 9 990171 10 19 326780 2 10 19019 5 16 455322 1 4 344048 5 10 588667 9 11 37976 6 13 334106 7 10 717507 1 6 68626 6 15 112119 12 20 109501 1 7 21340 4 12 834946 2 6 269561 2 5 76597 1 13 960908 8 16 621697 4 11 669598 5 15 574485 5 12 999888 8 19 367363 11 17 476696 8 18 221714 11 14 928464 16 18 776523 4 7 472565 2 7 806211 3 14 368079 14 18 654636 5 7 834152 17 19 150273 6 9 526059 79 140 30 1 2 975765 2 3 977342 3 4 952514 4 5 473457 5 6 207464 6 7 190891 7 8 276312 8 9 557587 9 10 707893 10 11 734917 11 12 290299 12 13 81109 13 14 973492 14 15 478758 15 16 489769 16 17 512728 17 18 501859 18 19 147328 19 20 359164 20 21 626900 21 22 505747 22 23 463709 23 24 954095 24 25 157338 25 26 383317 26 27 567240 27 28 299727 28 29 660389 29 30 436050 30 31 437277 31 32 10843 32 33 783943 33 34 666199 34 35 912775 35 36 215835 36 37 62852 37 38 69206 38 39 934437 39 40 999155 40 41 734487 41 42 707381 42 43 421367 43 44 238644 44 45 108023 45 46 143085 46 47 69704 47 48 885634 48 49 294092 49 50 881360 50 51 427890 51 52 801906 52 53 842176 53 54 688036 54 55 206188 55 56 390160 56 57 330373 57 58 225515 58 59 354382 59 60 297544 60 61 790373 61 62 70989 62 63 209888 63 64 235564 64 65 638408 65 66 34570 66 67 474169 67 68 497206 68 69 752785 69 70 435986 70 71 130885 71 72 858207 72 73 325482 73 74 191997 74 75 963614 75 76 508297 76 77 451005 77 78 808803 78 79 583085 48 69 31540 6 23 19149 44 59 733335 20 54 620052 33 36 829189 16 38 613308 31 47 951948 54 64 143012 3 13 675839 27 47 156699 23 51 29439 13 48 914709 51 59 980576 17 28 804889 25 30 205508 41 63 751822 27 35 798571 17 61 933788 34 78 303282 45 54 181228 54 58 444354 36 47 229172 28 39 953194 48 51 223799 27 49 98278 52 72 783253 18 43 147019 18 27 549655 3 11 936706 32 64 543573 6 26 984851 3 19 534536 22 75 237450 2 7 21355 17 34 847308 10 26 553715 20 58 618680 45 65 777719 30 45 886515 14 54 842917 21 56 651413 5 10 218543 7 57 572441 12 28 689877 74 76 299399 19 67 325300 28 32 805241 11 49 930120 7 13 518854 34 71 538460 3 39 592487 1 5 632877 8 21 418675 41 68 15889 5 35 582950 7 16 791289 28 66 724962 2 24 598448 12 33 351541 1 45 618971 41 43 215742 6 19 773600 91 135 10 1 2 498567 2 3 194299 3 4 73378 4 5 915679 5 6 22538 6 7 180381 7 8 888773 8 9 118156 9 10 779364 10 11 3380 11 12 217958 12 13 112462 13 14 769867 14 15 577568 15 16 811842 16 17 975732 17 18 966027 18 19 40605 19 20 463428 20 21 957380 21 22 893114 22 23 54786 23 24 296377 24 25 998100 25 26 602641 26 27 449869 27 28 288263 28 29 726749 29 30 374476 30 31 419210 31 32 201356 32 33 671438 33 34 748904 34 35 746545 35 36 345734 36 37 569578 37 38 386419 38 39 547314 39 40 8240 40 41 121777 41 42 801213 42 43 150607 43 44 648855 44 45 910689 45 46 430940 46 47 146469 47 48 910926 48 49 821343 49 50 843536 50 51 536367 51 52 908625 52 53 450733 53 54 709293 54 55 815324 55 56 632122 56 57 746819 57 58 495992 58 59 775663 59 60 476483 60 61 598823 61 62 895851 62 63 310412 63 64 41454 64 65 749717 65 66 632956 66 67 644919 67 68 384097 68 69 288958 69 70 970487 70 71 737910 71 72 919881 72 73 782931 73 74 853906 74 75 53251 75 76 173742 76 77 478995 77 78 347840 78 79 531963 79 80 583953 80 81 622827 81 82 351231 82 83 918349 83 84 902973 84 85 65830 85 86 925126 86 87 324120 87 88 625913 88 89 213621 89 90 835395 90 91 776698 9 42 730519 12 29 103917 15 86 385162 1 3 579316 48 71 622073 5 48 91216 60 70 102269 13 52 282614 40 59 738207 25 78 335852 4 9 736690 29 46 966199 16 23 495263 15 53 735572 65 70 235120 6 20 770800 58 71 844542 45 81 651987 1 45 379343 22 54 450339 15 62 227838 6 36 132476 3 7 211400 44 55 395510 78 86 816209 50 75 722814 22 30 25666 11 86 916577 40 44 213961 9 11 504783 23 27 852767 8 25 115436 11 39 590575 9 29 676276 58 72 959406 16 54 122466 2 65 476673 25 32 150754 2 69 604033 15 30 628218 14 39 456200 6 22 903068 22 32 146655 25 70 486790 1 58 808452 62 161 50 1 2 655517 2 3 772944 3 4 931514 4 5 714287 5 6 299310 6 7 366017 7 8 297620 8 9 276906 9 10 802143 10 11 431086 11 12 577702 12 13 839790 13 14 765858 14 15 14263 15 16 437566 16 17 903914 17 18 662432 18 19 265760 19 20 862284 20 21 362510 21 22 192722 22 23 686334 23 24 922783 24 25 995040 25 26 214439 26 27 573876 27 28 27832 28 29 115110 29 30 666608 30 31 388921 31 32 73898 32 33 205409 33 34 539488 34 35 690795 35 36 545118 36 37 664017 37 38 709093 38 39 508703 39 40 932880 40 41 49669 41 42 537729 42 43 719058 43 44 741244 44 45 844253 45 46 383997 46 47 423458 47 48 167532 48 49 640625 49 50 534055 50 51 868051 51 52 429902 52 53 368460 53 54 880199 54 55 322780 55 56 78973 56 57 201515 57 58 136781 58 59 863541 59 60 260037 60 61 794105 61 62 794566 43 48 12322 7 35 681486 23 26 904722 5 60 449643 7 44 115278 26 30 436398 17 21 886198 3 11 39114 15 20 209247 2 20 767525 2 5 680969 35 56 757445 2 39 302341 26 37 850910 4 51 692252 9 11 814096 7 53 258139 4 10 677305 31 56 901446 2 14 213196 39 44 511376 9 19 25939 50 57 891898 2 58 318503 2 55 814976 9 61 576513 3 12 707483 19 45 775197 32 36 717496 13 55 546681 15 33 654936 34 53 670491 23 42 152671 27 42 114325 8 30 771714 15 48 141175 9 12 812285 16 25 202003 6 24 784773 20 24 271610 7 47 674750 12 17 401311 2 17 773411 19 34 746600 54 56 876390 35 37 266670 11 37 358773 1 25 662897 29 38 713407 29 49 834360 25 46 957297 9 23 132928 2 25 459347 4 18 894947 1 11 26869 6 23 687352 34 36 267652 1 3 835593 11 26 382000 16 33 66804 3 18 944236 24 44 625369 11 18 959993 4 6 401062 22 29 242602 4 15 471929 10 39 456585 6 12 42639 1 5 417229 18 22 576857 2 13 943849 6 11 75481 23 33 803214 19 48 23124 1 13 411676 17 23 892934 12 38 44734 20 31 981602 14 46 95846 17 24 772458 15 28 491686 44 51 820516 15 21 611579 2 4 801276 31 37 755735 4 45 614518 1 4 539193 4 34 744055 29 36 46298 5 26 544108 43 54 381647 18 32 765632 1 18 618103 3 13 71001 32 47 972085 27 46 351015 8 31 214958 38 60 80284 22 40 780528 1 28 579404 20 84 7 1 2 702511 2 3 924057 3 4 200555 4 5 430461 5 6 831426 6 7 733332 7 8 489604 8 9 446993 9 10 67599 10 11 678098 11 12 94202 12 13 802038 13 14 677624 14 15 24015 15 16 53152 16 17 175439 17 18 96337 18 19 179217 19 20 517096 1 16 502282 12 14 928046 11 13 392016 2 4 521120 8 16 208234 15 18 236972 14 17 460456 10 17 555765 4 8 928402 1 4 975442 8 18 335596 2 10 441301 12 18 62283 11 19 687475 6 13 833199 6 9 338425 11 15 380940 1 3 288058 7 15 595225 13 19 623273 4 16 846120 17 19 795986 4 10 668859 16 19 916453 6 17 639858 3 8 111841 1 11 521913 1 10 866374 6 8 62270 1 7 469852 1 15 406839 6 12 725604 5 9 122784 1 9 601392 12 15 230360 10 12 606144 6 14 842693 10 19 502899 4 13 361005 9 14 772171 8 13 631689 5 10 140961 1 6 15617 10 15 942370 3 9 877098 11 18 419703 1 14 421221 5 11 588906 14 16 671050 15 19 942745 11 14 792183 10 14 448279 5 18 54155 1 5 702932 8 17 603928 10 16 280323 3 6 309162 1 18 791151 13 18 696831 7 14 61472 6 10 561713 4 6 83997 6 18 242413 5 13 544718 9 11 379232 28 63 13 1 2 26706 2 3 53762 3 4 796689 4 5 10261 5 6 49959 6 7 325679 7 8 586839 8 9 774081 9 10 201705 10 11 597647 11 12 97759 12 13 242442 13 14 851597 14 15 505789 15 16 258937 16 17 879556 17 18 222785 18 19 959634 19 20 375233 20 21 958204 21 22 515444 22 23 464574 23 24 772762 24 25 932611 25 26 100875 26 27 696217 27 28 560435 3 11 354579 5 9 81709 13 16 864462 6 10 867581 4 6 757663 7 20 42193 1 3 91926 3 9 28047 13 25 88937 5 10 580286 1 12 244405 15 25 349642 1 7 199793 10 16 487352 10 15 230939 4 7 269816 7 11 622345 1 14 683241 4 9 329611 20 23 670700 23 26 527538 5 8 483161 8 27 494222 14 23 907151 9 17 498219 9 20 593960 8 10 606849 3 22 893037 7 14 432025 8 11 483141 2 16 212271 3 20 299641 6 13 992344 11 19 166707 19 23 331961 13 23 261898 78 139 45 1 2 867672 2 3 733735 3 4 721441 4 5 195866 5 6 280941 6 7 460438 7 8 740314 8 9 648123 9 10 269344 10 11 641310 11 12 861806 12 13 58083 13 14 506306 14 15 616599 15 16 220920 16 17 306367 17 18 539240 18 19 996475 19 20 247065 20 21 969249 21 22 888255 22 23 496802 23 24 562180 24 25 411781 25 26 252184 26 27 863716 27 28 351775 28 29 786066 29 30 598513 30 31 811978 31 32 656055 32 33 534299 33 34 826155 34 35 829071 35 36 410881 36 37 586650 37 38 227806 38 39 98996 39 40 376066 40 41 926893 41 42 453642 42 43 540567 43 44 676202 44 45 404521 45 46 10655 46 47 685447 47 48 650157 48 49 306514 49 50 916171 50 51 576035 51 52 842590 52 53 485815 53 54 202664 54 55 582842 55 56 633938 56 57 217666 57 58 673734 58 59 514545 59 60 953762 60 61 723686 61 62 751420 62 63 829499 63 64 31147 64 65 188371 65 66 494284 66 67 245800 67 68 250637 68 69 904679 69 70 689303 70 71 875639 71 72 695621 72 73 40429 73 74 520404 74 75 376289 75 76 176460 76 77 826873 77 78 868321 29 77 805065 6 10 364487 17 58 281240 5 8 89421 5 43 362704 5 21 595022 38 45 832701 3 36 596879 5 31 245394 19 38 911184 30 60 364237 17 60 688622 2 25 329779 58 67 452942 56 60 683730 28 44 310447 16 20 506804 2 22 738916 5 16 512640 57 66 117131 44 63 408105 10 20 355497 2 66 860136 14 18 826208 9 39 597346 13 20 968865 17 31 882928 16 67 547448 2 6 965627 10 61 486913 19 36 930695 7 21 42046 16 22 382685 38 66 345772 1 3 377482 1 11 38890 14 19 853193 7 15 443362 3 46 919064 58 74 901996 59 61 421228 3 13 669326 30 35 895 14 30 474647 30 65 294254 24 47 246979 8 58 310063 2 18 864825 17 45 748385 22 33 841713 10 32 122412 26 37 784109 42 55 981480 23 45 780878 49 51 895604 35 60 608101 4 27 51587 5 10 365743 1 16 685203 12 16 497131 23 72 459467 16 47 790480 67 145 65 1 2 862919 2 3 86332 3 4 863063 4 5 624837 5 6 616759 6 7 524700 7 8 207234 8 9 775596 9 10 283025 10 11 401254 11 12 47492 12 13 573311 13 14 87185 14 15 304264 15 16 813260 16 17 682413 17 18 83182 18 19 102908 19 20 695401 20 21 305174 21 22 591138 22 23 122204 23 24 716243 24 25 551824 25 26 821412 26 27 955319 27 28 552589 28 29 540487 29 30 213504 30 31 956404 31 32 597662 32 33 132439 33 34 380453 34 35 654295 35 36 731519 36 37 169121 37 38 866638 38 39 589179 39 40 155568 40 41 208885 41 42 453147 42 43 355964 43 44 816440 44 45 469244 45 46 254747 46 47 986594 47 48 791673 48 49 975432 49 50 231683 50 51 333547 51 52 901732 52 53 783107 53 54 390520 54 55 714886 55 56 768177 56 57 798503 57 58 411522 58 59 970524 59 60 435516 60 61 823725 61 62 646288 62 63 863832 63 64 85998 64 65 538127 65 66 133563 66 67 768192 6 22 689398 3 42 404162 16 42 789495 3 59 277578 24 26 9181 20 64 59017 27 36 366639 38 52 427918 9 32 852340 1 11 659261 3 21 404651 1 5 474071 9 38 690075 2 42 565261 1 3 351368 53 63 533365 3 8 254718 19 34 198744 6 8 174475 45 66 747221 4 8 339909 2 15 672853 32 35 559323 8 40 65778 18 36 48567 1 21 760331 32 39 86 16 22 202307 2 29 500268 46 48 773880 2 8 451363 23 30 627423 14 23 25540 14 50 51015 58 61 942864 15 57 925763 15 22 283196 21 52 486927 11 40 515710 26 58 64409 17 46 232932 39 46 622792 52 59 22336 25 61 436076 8 34 975637 15 35 716706 41 52 999523 16 39 201486 8 14 704682 5 36 237605 26 28 518737 13 38 277904 3 5 126732 9 27 779255 6 18 127720 9 12 53010 4 17 991177 23 48 919383 9 18 385513 37 41 716848 1 38 168784 6 19 719148 5 13 231994 20 26 394465 4 9 314551 17 23 507296 42 66 937225 26 51 257671 15 47 81080 39 51 498093 4 48 550702 19 30 562894 11 49 914845 44 59 181778 14 16 606686 24 46 445485 34 38 494227 44 46 129932 9 45 758848 94 146 66 1 2 623255 2 3 225188 3 4 850718 4 5 968171 5 6 586221 6 7 782315 7 8 324050 8 9 900733 9 10 149792 10 11 148108 11 12 743727 12 13 371454 13 14 314734 14 15 461696 15 16 125149 16 17 223354 17 18 436299 18 19 41662 19 20 470649 20 21 849782 21 22 39581 22 23 922954 23 24 537417 24 25 917088 25 26 251171 26 27 993878 27 28 879449 28 29 560773 29 30 12550 30 31 25849 31 32 893577 32 33 238165 33 34 774695 34 35 143759 35 36 856275 36 37 6664 37 38 539321 38 39 329502 39 40 618173 40 41 422797 41 42 513467 42 43 430243 43 44 184921 44 45 591466 45 46 530770 46 47 553244 47 48 408158 48 49 916165 49 50 72599 50 51 160212 51 52 793650 52 53 162542 53 54 202279 54 55 394251 55 56 69119 56 57 779852 57 58 671725 58 59 39575 59 60 544126 60 61 26576 61 62 212478 62 63 614606 63 64 128218 64 65 121452 65 66 404559 66 67 500011 67 68 231762 68 69 895100 69 70 428208 70 71 64071 71 72 173477 72 73 186999 73 74 792971 74 75 690709 75 76 759068 76 77 683627 77 78 103697 78 79 675158 79 80 575933 80 81 547653 81 82 933690 82 83 85535 83 84 189481 84 85 873674 85 86 961113 86 87 465653 87 88 285463 88 89 656426 89 90 206080 90 91 841096 91 92 171276 92 93 120775 93 94 291944 20 70 715642 25 38 627464 13 48 400639 3 29 964737 5 17 892541 4 21 961008 2 4 429032 18 29 1162 28 84 512072 18 45 676507 50 62 939451 40 85 443367 6 9 642066 76 90 146038 32 57 873452 12 47 125514 10 55 943010 21 90 331514 33 41 538465 9 13 623398 7 51 864379 46 63 426027 9 75 148259 33 90 753353 9 18 85428 36 50 99384 10 61 523026 11 47 933953 18 24 630536 1 4 847525 3 57 626821 7 36 865854 1 41 952156 29 81 150863 15 89 300456 17 42 872422 29 35 369411 23 42 595902 19 44 917816 62 77 445062 17 60 437154 25 54 938332 28 62 170535 20 71 568076 18 22 13227 15 17 387900 16 33 83715 3 35 328343 25 51 66421 13 24 634848 89 91 669897 47 58 857102 4 15 697908 93 168 29 1 2 665477 2 3 472772 3 4 643864 4 5 219203 5 6 989903 6 7 414451 7 8 91496 8 9 97631 9 10 817970 10 11 94183 11 12 711296 12 13 583300 13 14 895223 14 15 386442 15 16 168291 16 17 944290 17 18 80615 18 19 709341 19 20 25891 20 21 304673 21 22 291906 22 23 398108 23 24 489539 24 25 704644 25 26 112789 26 27 894983 27 28 530245 28 29 576646 29 30 503380 30 31 653380 31 32 650178 32 33 405150 33 34 661245 34 35 940091 35 36 715991 36 37 364096 37 38 874278 38 39 572897 39 40 863492 40 41 132259 41 42 393898 42 43 157017 43 44 760235 44 45 748697 45 46 273003 46 47 583841 47 48 620970 48 49 517871 49 50 775926 50 51 77954 51 52 808579 52 53 545745 53 54 283568 54 55 126656 55 56 583140 56 57 298627 57 58 460013 58 59 798990 59 60 855255 60 61 789437 61 62 970476 62 63 935854 63 64 982383 64 65 550132 65 66 994110 66 67 319641 67 68 711491 68 69 477899 69 70 93324 70 71 521512 71 72 275933 72 73 514945 73 74 411695 74 75 380979 75 76 261630 76 77 681820 77 78 555119 78 79 150159 79 80 450741 80 81 206183 81 82 963802 82 83 433614 83 84 582873 84 85 63979 85 86 25152 86 87 836762 87 88 280054 88 89 634206 89 90 313941 90 91 200755 91 92 400965 92 93 485518 3 6 1139 54 88 290356 12 72 839856 21 40 740587 41 56 347309 12 35 351825 31 41 572848 10 22 875004 54 66 464127 15 19 15483 20 57 520265 35 85 273185 13 39 459946 41 43 130472 69 76 627352 1 6 592696 44 49 799955 4 25 119132 27 62 329861 27 35 900589 1 3 991749 1 41 352617 31 47 590903 3 29 439782 10 14 509492 11 69 640688 23 74 676608 37 88 717883 10 57 189002 16 43 254736 42 70 26819 1 31 251712 38 43 722411 8 69 381072 21 44 897161 25 45 198024 6 14 978050 16 63 351068 38 52 323531 5 89 746313 20 33 582113 31 43 668100 67 71 659549 58 72 691588 3 11 672326 2 56 250598 67 78 794843 47 61 811246 10 53 1823 25 70 322364 24 51 273911 30 86 570810 32 55 744640 7 74 931791 17 24 382869 35 61 920207 32 85 958575 58 60 733961 7 26 82111 6 8 707361 32 48 943029 14 21 780556 30 49 295965 20 83 406116 12 81 85334 75 85 934414 8 20 503524 47 84 866115 34 74 199081 12 82 197238 62 68 66868 78 87 728438 22 28 23881 49 71 202107 11 23 357055 40 88 320538
样例输出
4486239 1433889 1871446 1185713 3251794 6134304 2783053 8580401 17259603 10173234 576222 2157827 29615560 7219780 6459085 12335683 16774627 2324323 2185493 7745546