P14971 [HackerEarth] Pritam 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
普及
题目描述

Pritam 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. Portals 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 Pritam 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 portals 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 45 70 20 1 2 121345 2 3 581531 3 4 235962 4 5 197831 5 6 180126 6 7 851548 7 8 852169 8 9 306010 9 10 591900 10 11 325146 11 12 662440 12 13 443741 13 14 210937 14 15 13052 15 16 993626 16 17 523602 17 18 298421 18 19 887342 19 20 613180 20 21 910162 21 22 289022 22 23 587408 23 24 535344 24 25 772827 25 26 358827 26 27 366534 27 28 148619 28 29 832778 29 30 185353 30 31 468920 31 32 71948 32 33 587899 33 34 4908 34 35 122850 35 36 553022 36 37 189662 37 38 315045 38 39 780998 39 40 460768 40 41 618591 41 42 41886 42 43 363831 43 44 813642 44 45 853548 1 14 7745 10 19 216899 1 23 208830 10 17 56661 16 32 145483 29 37 290703 12 36 137184 2 5 123542 7 40 164441 1 13 642183 6 13 877328 1 20 683030 10 20 327884 2 40 6720 11 20 972365 19 44 174000 34 36 838677 18 22 997597 17 34 144789 24 35 214311 3 42 239622 10 43 896431 3 9 535361 1 9 134274 8 44 593885 3 7 251788 70 147 4 1 2 632594 2 3 249675 3 4 920603 4 5 894987 5 6 476128 6 7 133233 7 8 859390 8 9 720846 9 10 25893 10 11 249306 11 12 664257 12 13 454215 13 14 399741 14 15 213170 15 16 473316 16 17 123003 17 18 811345 18 19 623301 19 20 986339 20 21 998696 21 22 448449 22 23 958963 23 24 629815 24 25 584790 25 26 542617 26 27 808607 27 28 353236 28 29 387306 29 30 750300 30 31 2431 31 32 114427 32 33 242001 33 34 213130 34 35 983353 35 36 134164 36 37 720364 37 38 940655 38 39 245764 39 40 701548 40 41 930805 41 42 713167 42 43 163815 43 44 112547 44 45 927939 45 46 909898 46 47 920330 47 48 448397 48 49 36369 49 50 402631 50 51 301117 51 52 117835 52 53 824633 53 54 419983 54 55 993271 55 56 826039 56 57 8966 57 58 567873 58 59 102776 59 60 688237 60 61 117850 61 62 656398 62 63 275033 63 64 34834 64 65 844105 65 66 74436 66 67 287647 67 68 805853 68 69 343269 69 70 707978 6 56 661273 22 68 484951 6 43 612705 17 24 668392 24 60 180151 28 66 459097 23 46 261549 30 59 657255 17 46 755724 11 64 383102 8 19 153840 4 19 199919 42 56 766435 31 44 620571 12 20 339066 23 60 10314 55 68 707822 38 59 432948 3 10 73767 45 54 644749 15 18 340339 30 52 509788 2 46 867114 23 33 892030 2 65 48581 2 6 405833 7 47 50659 25 59 690801 31 39 87895 3 60 408471 1 23 218045 7 20 573869 5 60 177770 2 8 427394 35 47 773145 28 69 397974 9 23 368265 13 46 737004 13 61 954026 21 59 308247 3 29 863621 43 51 153085 20 31 826745 2 9 445258 26 44 577976 22 54 334713 52 63 752867 8 43 832506 13 26 305841 54 61 273722 10 34 137125 27 45 615630 23 26 362403 21 41 974863 44 66 739 21 52 95274 4 68 117208 35 57 653545 8 17 128878 4 6 145787 50 58 496678 21 64 849267 11 30 614917 23 66 732610 25 51 30930 11 24 552418 22 58 454618 6 26 6371 30 33 77850 6 42 600890 40 46 427391 10 12 222320 10 35 525712 19 25 540297 51 58 220331 5 10 974196 4 16 110009 36 41 127139 21 91 14 1 2 249462 2 3 915110 3 4 591175 4 5 80478 5 6 764577 6 7 71823 7 8 525208 8 9 859294 9 10 380747 10 11 116724 11 12 808293 12 13 842744 13 14 967849 14 15 568361 15 16 136240 16 17 164268 17 18 198291 18 19 648421 19 20 837038 20 21 226262 2 6 818553 1 12 754876 5 17 452374 2 10 710957 9 14 510018 8 11 389752 4 9 511246 1 15 388407 1 4 846331 2 4 19627 1 3 778973 4 12 534107 1 6 860259 6 12 420678 1 19 370332 2 5 357825 1 7 890820 3 13 776792 2 11 174311 11 17 996623 5 9 50646 6 15 43591 5 14 278032 3 7 337539 4 7 108736 7 18 424594 4 6 148605 11 16 820425 5 11 450203 4 10 309100 10 15 713615 14 17 363201 3 15 902381 4 13 40707 5 16 342273 10 18 169511 8 10 437800 9 11 479110 8 13 439838 9 15 684188 8 14 760276 7 9 409855 13 18 459669 4 18 980370 2 19 227518 10 19 128468 3 8 858691 3 5 654156 5 7 160149 10 14 945050 2 9 439798 5 10 206781 13 16 698923 15 20 564898 3 20 750420 10 16 681829 7 10 782809 4 15 490480 2 7 694648 4 8 947966 1 10 475934 4 11 90566 13 15 217755 7 19 787730 3 6 570806 8 16 693345 3 12 37354 11 13 307196 12 17 279063 17 19 905547 4 16 623173 31 57 6 1 2 896640 2 3 769505 3 4 845262 4 5 979297 5 6 538356 6 7 828880 7 8 774674 8 9 139201 9 10 243807 10 11 915984 11 12 283547 12 13 598935 13 14 194067 14 15 78036 15 16 420392 16 17 760981 17 18 325574 18 19 352568 19 20 819985 20 21 381654 21 22 628228 22 23 69495 23 24 862304 24 25 771253 25 26 393439 26 27 846617 27 28 920419 28 29 628103 29 30 458141 30 31 715372 3 17 186054 1 24 316954 8 11 286307 12 16 906556 2 5 23500 3 18 932409 2 12 996291 15 22 628390 3 5 331854 25 28 807199 22 25 985916 5 7 475552 1 3 66672 2 17 38159 11 22 971328 5 29 161142 18 24 547416 2 4 359812 6 14 38887 1 10 618110 22 24 821236 21 26 764916 10 26 665861 3 13 278562 18 20 917835 18 23 825415 15 20 598643 26 75 19 1 2 839051 2 3 713873 3 4 244537 4 5 151697 5 6 799316 6 7 374775 7 8 110706 8 9 474174 9 10 628570 10 11 250442 11 12 573324 12 13 783605 13 14 313914 14 15 777164 15 16 195201 16 17 127877 17 18 691632 18 19 591344 19 20 998291 20 21 785584 21 22 93510 22 23 177906 23 24 207923 24 25 967565 25 26 636957 12 19 566620 2 10 799273 2 24 30450 1 3 184402 15 17 221044 7 23 224621 13 19 204700 8 19 341009 14 17 512303 1 4 630762 4 7 665937 1 20 314917 9 17 625211 6 15 107112 2 8 954231 3 20 101624 1 6 987988 2 4 61617 15 20 801601 2 17 43265 9 16 374186 2 9 277734 5 19 383597 3 7 817359 3 17 842241 9 25 766676 3 6 111484 4 8 404780 5 24 538439 10 19 972615 14 19 97068 7 20 50476 1 8 602428 7 13 989877 11 24 281199 3 10 738321 10 23 501209 6 13 399829 2 5 14387 15 21 652437 4 6 117314 8 10 415416 14 23 8167 1 7 774290 9 18 369770 6 21 122295 3 14 841218 5 13 876164 17 25 941741 6 12 477379 34 118 32 1 2 613603 2 3 941300 3 4 3654 4 5 980943 5 6 853367 6 7 139702 7 8 472555 8 9 374284 9 10 514303 10 11 968931 11 12 415304 12 13 825107 13 14 824725 14 15 825203 15 16 923310 16 17 519732 17 18 713215 18 19 737396 19 20 814719 20 21 913124 21 22 301265 22 23 372618 23 24 783474 24 25 564641 25 26 313146 26 27 21833 27 28 287429 28 29 986907 29 30 735233 30 31 123910 31 32 957725 32 33 951303 33 34 139381 5 8 78649 4 19 192057 3 6 798235 3 21 871287 20 22 366959 20 29 729818 13 23 626612 2 18 197558 13 18 421079 9 19 360461 10 20 928193 4 7 737871 8 23 833428 7 11 18087 2 25 897554 1 14 923390 18 20 172134 4 18 339826 11 16 562673 5 25 677542 8 19 730152 1 10 553293 9 27 267698 1 4 744679 7 12 298208 11 27 406099 14 23 796359 2 11 953941 7 18 107234 20 25 954745 6 16 132340 15 17 888019 10 13 294239 10 27 640282 11 15 298969 3 9 577834 8 20 711681 6 26 168406 17 32 519506 1 20 63768 11 21 10157 4 9 458136 1 9 611538 6 12 68408 6 8 358798 8 11 36133 9 13 328797 13 28 309267 15 21 408346 9 18 786047 16 33 271447 1 8 470656 5 19 383208 17 28 227219 17 27 421000 13 26 989370 17 24 960455 5 30 64827 1 6 255372 7 30 350299 4 11 885701 12 21 142231 11 24 94552 6 25 792758 23 25 724538 19 29 520624 2 23 670324 7 9 407448 19 25 759285 19 32 274715 13 24 267438 16 25 447421 19 24 354040 9 11 206718 3 18 765790 2 17 673682 6 10 761618 10 15 653653 9 17 684516 2 8 912452 24 30 677567 8 32 352389 2 32 344107 23 27 708897 15 27 239299 12 19 9 1 2 218058 2 3 228651 3 4 153438 4 5 563582 5 6 158505 6 7 581483 7 8 832048 8 9 854826 9 10 919807 10 11 504694 11 12 461104 3 11 355532 7 10 938503 1 3 370208 4 7 436030 2 11 355600 7 9 330013 1 4 91379 3 6 644025 66 103 21 1 2 835371 2 3 336214 3 4 577193 4 5 500611 5 6 768592 6 7 369237 7 8 906817 8 9 625194 9 10 980912 10 11 69282 11 12 453584 12 13 673040 13 14 862788 14 15 869596 15 16 115551 16 17 781719 17 18 802945 18 19 117509 19 20 635057 20 21 283357 21 22 13946 22 23 700156 23 24 604901 24 25 512611 25 26 503683 26 27 366329 27 28 514837 28 29 903334 29 30 826596 30 31 294720 31 32 788480 32 33 863883 33 34 654723 34 35 541669 35 36 536026 36 37 710310 37 38 551826 38 39 397259 39 40 175467 40 41 891415 41 42 535082 42 43 699365 43 44 325611 44 45 274650 45 46 890919 46 47 112362 47 48 247658 48 49 721119 49 50 431980 50 51 915610 51 52 722559 52 53 845511 53 54 202677 54 55 927761 55 56 757363 56 57 41006 57 58 955098 58 59 629503 59 60 60089 60 61 933462 61 62 538319 62 63 802874 63 64 812691 64 65 939179 65 66 507038 6 45 18784 1 8 37733 49 56 694863 1 46 4930 25 62 584159 25 60 214051 19 29 391674 18 29 409862 11 27 444012 7 42 153696 35 55 588701 16 63 820550 6 44 252657 1 4 945437 25 58 960256 20 25 484402 4 8 461572 1 10 849577 37 53 529900 9 53 174274 28 39 485369 29 58 428253 6 27 271904 20 26 267145 7 14 339521 22 30 142107 9 12 129899 10 16 718189 9 56 779825 32 49 836186 8 48 195364 19 58 448178 49 54 48793 36 43 325944 4 16 555267 2 8 921268 26 37 30035 8 37 876758 66 110 61 1 2 951754 2 3 394572 3 4 173325 4 5 31970 5 6 367867 6 7 482309 7 8 516372 8 9 901212 9 10 446754 10 11 391269 11 12 289052 12 13 643183 13 14 42742 14 15 988904 15 16 253836 16 17 314255 17 18 393306 18 19 833961 19 20 478069 20 21 598223 21 22 125279 22 23 471054 23 24 491799 24 25 437415 25 26 161743 26 27 599733 27 28 713467 28 29 58348 29 30 782699 30 31 620106 31 32 473011 32 33 51718 33 34 369674 34 35 510367 35 36 293576 36 37 318189 37 38 910352 38 39 334292 39 40 38834 40 41 439412 41 42 323991 42 43 642534 43 44 135896 44 45 821341 45 46 941950 46 47 409870 47 48 468098 48 49 344316 49 50 473900 50 51 635212 51 52 199605 52 53 601647 53 54 226757 54 55 908566 55 56 766826 56 57 42773 57 58 181832 58 59 841188 59 60 775610 60 61 368992 61 62 716240 62 63 878115 63 64 693924 64 65 573904 65 66 957292 3 39 126108 18 39 22860 23 37 599653 29 36 199840 10 46 676513 3 34 503295 9 12 589116 5 35 594972 16 22 95132 16 25 410524 11 65 350846 19 31 283504 29 57 238708 41 57 215995 6 11 441352 13 64 396774 25 33 460397 3 6 422837 17 33 290467 6 29 188468 8 10 273515 36 43 846636 3 44 843461 15 61 847707 27 43 594289 9 14 934179 2 14 12975 11 46 791570 14 17 384359 25 36 127067 5 52 307807 57 60 405723 8 12 771712 16 37 494696 16 32 671657 19 42 188373 1 43 256200 21 62 290972 29 38 76709 15 44 110189 38 46 557020 40 59 367899 19 23 176804 18 57 678787 29 33 239641 63 126 38 1 2 88036 2 3 299907 3 4 378960 4 5 479646 5 6 178671 6 7 409930 7 8 650896 8 9 528240 9 10 596433 10 11 653187 11 12 656135 12 13 771462 13 14 107835 14 15 219946 15 16 694284 16 17 89371 17 18 402817 18 19 129093 19 20 423515 20 21 953383 21 22 299502 22 23 422172 23 24 864963 24 25 342400 25 26 105513 26 27 704363 27 28 321308 28 29 72153 29 30 54838 30 31 869208 31 32 217431 32 33 573344 33 34 665894 34 35 887015 35 36 672386 36 37 877457 37 38 950857 38 39 581606 39 40 48907 40 41 479428 41 42 784960 42 43 360297 43 44 2440 44 45 611727 45 46 682204 46 47 521096 47 48 869799 48 49 684244 49 50 130292 50 51 189907 51 52 797764 52 53 23669 53 54 46114 54 55 696275 55 56 44428 56 57 153104 57 58 264971 58 59 737076 59 60 118672 60 61 160017 61 62 503021 62 63 99894 23 36 439953 17 57 984588 14 21 582878 19 42 694186 12 47 952149 3 18 224008 2 4 230166 2 15 149754 1 26 426683 13 60 305211 1 3 428333 41 46 928388 4 10 45766 10 26 500858 11 24 940736 42 49 671243 29 31 229307 4 28 263798 1 17 472676 14 24 845902 22 37 477070 48 52 981831 26 56 510653 12 51 264814 39 52 854874 24 59 100779 37 39 272276 16 24 623846 52 56 824746 10 47 560383 7 17 357878 17 27 482186 42 57 321968 12 50 912990 8 48 493303 13 19 383016 20 23 638295 9 17 477490 3 10 249361 11 23 855882 1 37 238257 5 22 170275 2 33 737121 7 10 243169 1 4 63118 49 52 779554 1 7 992940 6 16 44521 6 55 758251 4 15 640775 2 24 56504 2 31 150336 11 48 690064 50 57 571181 25 40 603871 34 56 571756 3 57 4900 31 50 165267 37 55 539729 6 17 919881 10 51 326832 13 33 879440 35 37 95560 22 38 888692 27 102 8 1 2 5904 2 3 473985 3 4 438047 4 5 95157 5 6 301705 6 7 167307 7 8 909851 8 9 21762 9 10 328928 10 11 390401 11 12 261703 12 13 228967 13 14 830458 14 15 666857 15 16 972737 16 17 665543 17 18 230817 18 19 279591 19 20 971546 20 21 143327 21 22 700157 22 23 731511 23 24 289264 24 25 971098 25 26 401434 26 27 636107 18 20 981149 4 7 466443 1 4 988361 2 5 900824 8 13 72003 6 19 869478 15 26 420410 23 25 530047 2 4 220552 3 9 626133 11 16 703131 4 16 806279 9 11 32527 5 16 236319 2 6 105461 7 25 317072 4 15 334906 10 16 583718 2 8 187360 6 21 357213 11 24 663261 5 12 686284 9 23 880844 12 26 446405 13 25 926948 11 25 84808 3 25 17855 8 22 738198 9 16 659766 11 15 490074 2 23 496709 9 17 357821 2 24 382998 8 19 680582 4 9 797088 4 6 29769 3 6 908738 6 16 430660 5 7 793561 9 26 546026 5 11 193270 7 13 651866 1 7 630499 4 20 394061 9 18 916854 12 15 824935 1 9 841469 2 20 556396 11 20 284793 6 12 281308 1 6 659113 2 13 23193 18 22 297216 8 16 166508 1 22 790194 7 21 423901 15 21 28834 2 7 146109 3 18 61703 4 18 133222 6 17 937254 6 13 617454 6 18 335855 7 12 192450 5 13 23942 8 12 496727 11 14 984033 2 22 875266 1 3 746606 7 16 322594 2 15 231325 3 10 649291 2 19 936355 3 19 860925 21 23 962882 6 15 655310 75 120 8 1 2 330792 2 3 990409 3 4 92236 4 5 502401 5 6 192990 6 7 82737 7 8 300471 8 9 407607 9 10 575691 10 11 810052 11 12 831728 12 13 627652 13 14 641324 14 15 62395 15 16 625556 16 17 829481 17 18 445754 18 19 494957 19 20 414810 20 21 801620 21 22 764714 22 23 353739 23 24 14952 24 25 126991 25 26 653659 26 27 72041 27 28 378285 28 29 274435 29 30 871152 30 31 256578 31 32 150586 32 33 424227 33 34 560643 34 35 533759 35 36 550050 36 37 960409 37 38 544016 38 39 227917 39 40 578331 40 41 483779 41 42 621916 42 43 389595 43 44 937079 44 45 882004 45 46 743935 46 47 160561 47 48 402172 48 49 818848 49 50 432937 50 51 134178 51 52 81972 52 53 704918 53 54 797131 54 55 435439 55 56 833459 56 57 779736 57 58 997620 58 59 217652 59 60 954740 60 61 409505 61 62 999285 62 63 488241 63 64 190597 64 65 748987 65 66 318326 66 67 36190 67 68 688356 68 69 14306 69 70 9779 70 71 68908 71 72 618978 72 73 729461 73 74 441799 74 75 76726 8 19 927167 30 56 451144 3 71 630265 36 41 750886 36 64 557862 2 42 900074 19 62 785689 11 15 421294 47 50 866621 48 70 422248 22 27 666533 50 61 311290 15 26 220736 1 5 804682 43 62 224792 32 57 254705 3 46 368315 25 43 871156 27 36 945636 8 35 277775 38 41 332506 27 38 740036 13 22 921804 16 52 278315 19 68 866756 11 16 253956 26 55 434391 13 74 39949 4 6 353919 12 18 29367 34 66 844545 29 53 291448 46 50 739149 9 40 4607 42 61 783011 12 22 582250 7 18 344999 19 38 454514 23 48 106111 33 48 828935 17 53 311994 9 16 750962 12 14 752105 10 26 846538 29 51 449920 19 30 475471 73 88 67 1 2 96529 2 3 530026 3 4 72978 4 5 651430 5 6 246031 6 7 804279 7 8 437122 8 9 614550 9 10 261207 10 11 529099 11 12 676316 12 13 912149 13 14 341310 14 15 775462 15 16 762813 16 17 716521 17 18 630266 18 19 760433 19 20 805639 20 21 531592 21 22 755859 22 23 377032 23 24 115966 24 25 283503 25 26 865686 26 27 943653 27 28 438757 28 29 866011 29 30 339696 30 31 259298 31 32 965482 32 33 910743 33 34 538513 34 35 176697 35 36 218084 36 37 706104 37 38 818654 38 39 589396 39 40 310311 40 41 756555 41 42 725343 42 43 10738 43 44 759612 44 45 685013 45 46 614593 46 47 841940 47 48 953469 48 49 673221 49 50 929607 50 51 363336 51 52 924333 52 53 141479 53 54 363280 54 55 554489 55 56 711294 56 57 903395 57 58 96571 58 59 199305 59 60 571995 60 61 484643 61 62 464043 62 63 709746 63 64 99223 64 65 762907 65 66 778101 66 67 292893 67 68 163511 68 69 377247 69 70 717732 70 71 351727 71 72 323963 72 73 425707 37 43 467413 2 4 159843 14 58 159860 11 71 410518 44 46 61638 11 58 767941 37 39 164826 19 65 36058 2 7 72661 58 66 462022 6 53 592186 9 45 451971 2 49 363003 9 28 393406 15 57 148558 42 54 586217 79 107 23 1 2 251498 2 3 400558 3 4 382128 4 5 537840 5 6 310491 6 7 537163 7 8 169722 8 9 617862 9 10 326182 10 11 328436 11 12 247187 12 13 216026 13 14 632844 14 15 89713 15 16 80038 16 17 201188 17 18 968228 18 19 792278 19 20 564991 20 21 152618 21 22 536139 22 23 899822 23 24 814578 24 25 128876 25 26 82714 26 27 757978 27 28 925827 28 29 87336 29 30 363947 30 31 370714 31 32 375386 32 33 889050 33 34 348557 34 35 507207 35 36 626831 36 37 72078 37 38 981573 38 39 549580 39 40 869706 40 41 319046 41 42 302166 42 43 262763 43 44 411767 44 45 551707 45 46 591384 46 47 958111 47 48 886134 48 49 200230 49 50 452173 50 51 42237 51 52 599480 52 53 643215 53 54 17372 54 55 287783 55 56 339013 56 57 69486 57 58 193403 58 59 468150 59 60 229934 60 61 763549 61 62 918452 62 63 552505 63 64 510629 64 65 430834 65 66 15195 66 67 789945 67 68 887897 68 69 411387 69 70 979980 70 71 508497 71 72 778172 72 73 132508 73 74 931756 74 75 521162 75 76 904290 76 77 768306 77 78 594828 78 79 297325 17 32 947444 33 78 759243 55 74 242473 27 31 801222 21 27 513901 15 60 290951 1 6 366558 14 60 997553 14 16 658102 18 76 314134 1 46 710589 3 17 376838 33 39 941639 12 19 186960 36 61 670228 30 35 480701 10 28 703548 2 51 144599 22 38 606497 15 21 309406 1 25 625748 12 16 58831 5 29 725436 48 52 109433 9 12 377055 23 55 756138 47 65 569566 32 46 396932 26 63 252403 25 44 21 1 2 218842 2 3 715736 3 4 670648 4 5 488763 5 6 250105 6 7 294893 7 8 528161 8 9 340998 9 10 553868 10 11 755124 11 12 454509 12 13 414814 13 14 430239 14 15 270056 15 16 918068 16 17 315704 17 18 256887 18 19 605678 19 20 181513 20 21 396114 21 22 489313 22 23 141766 23 24 258204 24 25 69143 17 24 274501 1 6 57432 6 11 879841 10 15 535605 1 4 888296 9 17 161145 5 15 744352 12 19 342960 2 13 435671 1 3 835717 7 11 444495 10 16 454580 11 13 260549 4 7 662673 2 8 486235 8 19 418881 7 18 233962 20 23 388578 5 11 807138 8 12 489254 86 165 43 1 2 736337 2 3 872194 3 4 591967 4 5 548179 5 6 765753 6 7 15798 7 8 534018 8 9 968269 9 10 420509 10 11 398417 11 12 611606 12 13 720111 13 14 162638 14 15 911077 15 16 741083 16 17 855907 17 18 126318 18 19 769658 19 20 473291 20 21 497443 21 22 391403 22 23 147145 23 24 551199 24 25 611222 25 26 183823 26 27 990762 27 28 262072 28 29 368272 29 30 920550 30 31 245502 31 32 897104 32 33 248470 33 34 537143 34 35 58771 35 36 183223 36 37 971372 37 38 795897 38 39 331615 39 40 57666 40 41 736369 41 42 555429 42 43 375292 43 44 10168 44 45 7563 45 46 385425 46 47 635776 47 48 215149 48 49 410920 49 50 364809 50 51 997020 51 52 222636 52 53 38064 53 54 399090 54 55 346260 55 56 58473 56 57 786384 57 58 211848 58 59 878001 59 60 649590 60 61 844519 61 62 316768 62 63 552661 63 64 683082 64 65 653351 65 66 655976 66 67 542500 67 68 938246 68 69 232298 69 70 253009 70 71 292668 71 72 646058 72 73 325061 73 74 823647 74 75 85369 75 76 975538 76 77 770609 77 78 358198 78 79 622621 79 80 570518 80 81 874269 81 82 361596 82 83 533403 83 84 71148 84 85 42605 85 86 99094 55 73 709836 20 35 749014 13 29 206883 13 15 350083 36 71 249001 30 58 85560 4 85 954785 73 78 430610 38 62 373507 54 59 288200 17 39 640083 1 8 202900 14 17 532678 3 20 632292 14 28 503631 11 79 762615 59 84 229980 46 76 724932 13 23 446294 20 72 528364 6 65 600627 23 31 359361 21 30 501030 4 6 774914 11 19 895944 66 80 362696 4 16 863721 20 22 653859 21 49 370214 14 83 482418 23 26 133983 7 81 869302 17 46 359655 60 62 681249 1 26 170554 16 50 398868 2 11 264128 26 31 851374 22 30 642089 57 63 976727 7 25 283912 9 25 503891 3 24 143084 15 65 841094 23 61 802202 52 79 57503 8 10 345511 60 73 225721 11 38 835395 4 81 110752 1 6 491570 13 59 32492 12 19 287542 65 70 703353 5 8 785429 34 71 770733 6 58 655188 9 82 689735 38 63 411400 14 50 263149 4 32 864121 5 40 195924 3 15 330797 9 48 692449 72 76 634277 12 69 400494 15 47 854149 7 47 293704 6 10 41965 11 20 475056 49 64 942687 18 20 282697 50 76 942588 31 38 26064 23 27 55490 20 29 269071 38 73 592232 15 19 499603 46 60 597688 14 22 65244 84 136 48 1 2 798430 2 3 9602 3 4 392602 4 5 967476 5 6 269073 6 7 45912 7 8 401570 8 9 514611 9 10 82766 10 11 331877 11 12 85045 12 13 286814 13 14 303687 14 15 796499 15 16 25162 16 17 450415 17 18 385691 18 19 508337 19 20 665036 20 21 632700 21 22 686822 22 23 628258 23 24 402594 24 25 665025 25 26 947239 26 27 496656 27 28 247442 28 29 192961 29 30 29927 30 31 597208 31 32 871230 32 33 908266 33 34 540301 34 35 724274 35 36 621843 36 37 879403 37 38 752863 38 39 590016 39 40 290382 40 41 572229 41 42 607195 42 43 263281 43 44 751453 44 45 367903 45 46 562357 46 47 911890 47 48 655952 48 49 994054 49 50 458187 50 51 955196 51 52 544732 52 53 433617 53 54 163221 54 55 138565 55 56 55331 56 57 313711 57 58 962590 58 59 409107 59 60 640954 60 61 20450 61 62 778508 62 63 508171 63 64 844938 64 65 198086 65 66 847908 66 67 13485 67 68 181572 68 69 338237 69 70 927362 70 71 944975 71 72 556730 72 73 423142 73 74 532164 74 75 155903 75 76 459205 76 77 920495 77 78 533276 78 79 57977 79 80 951497 80 81 983072 81 82 587878 82 83 766816 83 84 596293 4 8 89368 2 49 666127 7 53 363068 24 37 782874 26 31 847209 63 73 962956 47 81 774760 9 36 352355 12 35 353034 26 78 985549 2 11 84683 32 67 812301 12 16 211662 73 78 542656 2 6 761240 3 35 631689 25 41 23536 22 57 894174 53 75 692077 11 62 226042 18 65 926600 59 73 145046 20 23 365676 32 63 848374 63 68 820371 23 45 321012 35 42 777833 51 54 517457 7 11 130874 9 53 473977 4 37 249084 5 23 385833 5 55 189492 39 69 348559 37 79 698635 42 63 137914 35 64 200191 29 43 951450 22 74 939238 1 21 375334 41 56 124953 50 57 425003 3 60 965336 32 82 600650 32 48 445781 17 46 446749 24 26 682378 31 80 889159 55 80 923041 4 39 879319 9 67 179725 41 57 554820 48 57 908653 25 95 17 1 2 754231 2 3 576777 3 4 808289 4 5 24318 5 6 526377 6 7 909972 7 8 3258 8 9 713854 9 10 902585 10 11 157056 11 12 335259 12 13 321263 13 14 703586 14 15 677592 15 16 834047 16 17 593180 17 18 688113 18 19 359331 19 20 49493 20 21 636663 21 22 653098 22 23 902545 23 24 242748 24 25 258445 6 9 230179 4 6 934415 2 4 298946 3 5 770983 8 19 932251 1 7 470970 4 16 282791 10 17 389156 12 21 340315 13 16 82843 6 10 884199 2 8 428062 2 7 784777 1 14 380833 16 18 246561 4 21 655057 20 22 948783 1 10 602860 9 18 374473 6 22 480055 10 14 705619 15 21 518871 4 7 108740 15 18 222668 2 9 547363 1 17 482845 2 10 470708 13 23 97975 5 9 92188 2 11 393784 3 6 682715 6 21 649746 1 12 835141 1 9 250607 1 3 699438 12 14 774649 2 17 838243 1 5 161231 11 14 417653 18 20 609850 3 11 126481 9 16 914132 11 17 935401 8 11 353279 2 18 861667 16 23 415379 8 14 445431 4 11 678775 5 12 165859 15 22 960714 10 23 440122 12 17 140535 16 21 977413 4 22 463562 4 10 972272 14 22 187802 10 15 121536 12 23 611664 2 16 752714 9 11 292707 5 17 469264 7 11 816575 18 23 623639 12 20 946660 5 8 736723 1 6 392435 17 23 135914 11 13 111414 3 24 726850 22 24 366729 3 7 118906 26 119 25 1 2 896475 2 3 669372 3 4 684195 4 5 923864 5 6 132669 6 7 981829 7 8 437516 8 9 101610 9 10 761969 10 11 84058 11 12 57489 12 13 642612 13 14 728946 14 15 313959 15 16 149344 16 17 640442 17 18 160170 18 19 31629 19 20 533449 20 21 964348 21 22 889304 22 23 935640 23 24 971218 24 25 853365 25 26 632227 3 5 462746 2 4 925884 12 16 72523 3 13 859754 3 9 918264 1 22 468352 8 20 68557 5 9 442188 4 16 212239 5 20 780793 4 8 896239 7 17 142109 16 22 318011 14 16 523851 1 18 403957 5 7 64840 7 23 318092 6 11 409658 6 15 200895 18 24 285037 11 15 1799 2 10 626602 2 19 145525 1 4 693383 1 9 604106 4 6 748082 5 16 308093 6 21 533573 13 17 850552 23 25 948810 1 19 49715 5 21 1323 3 21 820881 1 3 522015 14 22 895565 4 10 412675 5 22 445984 17 20 363183 2 5 478107 1 5 342502 6 18 841014 1 8 804519 9 11 265764 15 19 793705 9 15 492263 7 15 319425 10 19 101594 14 18 882956 9 13 916555 15 18 933252 7 22 370031 3 18 470567 5 23 398502 6 20 340411 11 16 708730 2 22 452302 14 23 133695 14 25 142847 4 14 340970 5 15 698229 5 8 856383 10 16 179863 1 16 783008 6 12 813572 15 22 613435 5 13 583648 14 17 267606 2 13 738343 3 22 327619 11 17 690504 16 24 858693 13 19 50164 15 24 460041 4 18 568520 14 20 905862 3 7 332979 13 18 643693 13 24 131474 2 11 659505 10 13 950900 3 19 41306 4 11 314455 9 14 690364 3 24 438597 6 8 537510 9 21 745123 7 16 38699 7 18 240220 3 6 449619 1 6 21448 14 21 185962 2 9 115132 9 16 17270 11 13 368684 66 136 28 1 2 971461 2 3 777585 3 4 834958 4 5 548293 5 6 329303 6 7 614012 7 8 613784 8 9 866961 9 10 987149 10 11 338122 11 12 848870 12 13 953999 13 14 458839 14 15 743484 15 16 917396 16 17 227337 17 18 530548 18 19 714019 19 20 438465 20 21 225547 21 22 532651 22 23 536863 23 24 313979 24 25 554381 25 26 435222 26 27 603914 27 28 239314 28 29 713940 29 30 187463 30 31 97318 31 32 41680 32 33 817134 33 34 113000 34 35 122018 35 36 538985 36 37 59347 37 38 50214 38 39 936524 39 40 494630 40 41 168562 41 42 315477 42 43 726715 43 44 639526 44 45 555910 45 46 7897 46 47 92729 47 48 902433 48 49 470503 49 50 144071 50 51 369793 51 52 85283 52 53 998692 53 54 58259 54 55 512375 55 56 340615 56 57 518513 57 58 17627 58 59 138229 59 60 908199 60 61 802208 61 62 291068 62 63 206399 63 64 991033 64 65 332028 65 66 623178 1 4 749755 9 46 940053 11 33 767486 12 19 840716 2 54 495104 2 4 790830 2 5 928297 2 6 747199 10 17 585939 1 3 479613 4 6 37224 52 59 233998 29 43 380478 21 36 899711 13 50 549910 38 60 409241 14 27 440385 48 52 267246 17 41 957135 18 35 443238 4 24 120858 19 29 535751 5 10 596382 31 39 264941 8 24 55904 30 38 217767 38 56 520662 8 13 233696 26 39 934645 6 11 482224 35 51 884205 30 52 442938 6 29 407899 17 52 953041 8 12 527419 6 36 439982 5 58 335713 24 49 589760 27 39 544899 13 41 511829 7 36 455296 28 35 58842 19 22 634932 20 24 843214 10 18 935826 1 14 302958 21 27 130583 6 8 328337 12 55 982358 15 59 559584 17 22 554303 7 21 483311 2 12 32612 25 50 545158 6 23 176789 6 17 905363 3 63 899544 2 10 804680 3 43 147577 9 14 80393 43 64 789975 12 23 352198 3 14 61143 3 16 958721 13 25 338756 6 32 465830 21 24 979866 24 28 304559 5 11 52104 30 43 451702 6 14 523760
样例输出
1075546 1293332 909805 17960603 107093 3970704 2778987 9481960 990859 1537677 895083 6783677 17411444 1756889 3798778 769928 9075607 327379 0 2988682