#864. 1868. MinCut Query

1868. MinCut Query

#1868. MinCut Query

题目描述

N 个点 M 条边的无向带权图,求所有 s,t(s <t),求出 s t 的最小割的容量(原题相当于这个意思)。

约束条件 : 数据组数 _T ≤20 , N ≤150, M ≤3000 _

输入格式

输出格式

样例

样例输入

11  

24 87  

10 20 747794  

8 11 760493  

10 14 202363  

20 3 520060  

12 23 180541  

19 5 455737  

12 9 702568  

22 15 21531  

15 20 174068  

8 18 979803  

7 19 133070  

16 2 18457  

20 11 176230  

24 9 898538  

15 21 798316  

19 6 803527  

20 21 759957  

10 15 999171  

5 2 702306  

22 21 336328  

9 18 750847  

10 2 925858  

13 16 819583  

10 15 233368  

3 21 344044  

15 8 426809  

13 3 695789  

1 4 502652  

3 8 999933  

13 21 993369  

20 5 636227  

19 7 297540  

4 11 651435  

11 12 66602  

18 15 573318  

13 5 260757  

14 9 724287  

2 10 429690  

5 12 558441  

10 16 108118  

10 12 834482  

12 22 698928  

16 17 179498  

10 19 276966  

11 12 406220  

9 17 332872  

21 6 409504  

12 7 363369  

5 12 226341  

22 13 700724  

3 14 122847  

4 2 243556  

12 17 537765  

21 2 792351  

2 5 757035  

5 13 324915  

12 9 373744  

4 12 148366  

4 17 151433  

24 6 899229  

12 24 901475  

2 3 794396  

6 14 908236  

2 3 894429  

16 4 335929  

10 9 322405  

6 3 118607  

11 1 670689  

10 22 569918  

13 21 987744  

7 24 298491  

12 5 206726  

5 7 617506  

12 3 469787  

22 3 308543  

9 14 939508  

4 5 376349  

12 15 127829  

12 16 195747  

9 5 755423  

24 11 267606  

2 14 473731  

23 18 229321  

9 5 248627  

19 18 586709  

17 19 213259  

21 22 442063  

5  

8962600  

6532036  

8433452  

3911899  

1419379  

31 269  

3 9 487132  

25 31 808934  

25 5 370164  

24 26 548900  

1 30 713774  

19 16 187191  

23 29 116467  

27 30 422091  

26 15 855543  

1 3 517446  

27 6 418419  

1 28 103349  

5 20 262010  

12 10 166343  

21 10 319302  

17 27 575322  

20 21 229905  

18 20 73941  

30 23 346229  

31 1 565985  

3 16 789225  

28 2 821397  

16 21 740085  

26 3 207673  

2 12 905386  

28 4 306641  

13 23 340714  

22 8 280525  

23 4 108582  

25 3 937733  

19 5 218005  

14 31 85274  

14 15 247256  

22 9 575580  

18 11 223206  

30 5 962505  

26 15 262755  

11 5 518945  

13 26 723507  

7 19 222843  

30 4 235190  

6 18 849959  

13 29 518809  

8 17 383304  

11 9 999755  

13 17 690369  

28 16 238047  

1 21 66250  

26 29 3034  

11 6 910254  

15 19 519126  

30 29 245976  

27 23 703730  

12 25 253415  

13 2 26305  

13 14 278051  

7 10 308903  

11 9 858700  

28 1 132003  

18 12 144501  

6 24 908539  

29 20 522536  

1 15 171693  

10 24 720505  

22 6 590965  

9 16 495344  

14 22 202901  

2 1 416950  

7 27 717989  

12 13 40744  

20 17 658391  

15 12 553542  

6 10 174233  

21 20 690361  

25 8 266762  

1 17 903191  

20 28 806368  

15 29 730691  

18 5 226058  

21 14 328206  

3 2 947387  

5 14 602727  

27 20 56553  

29 7 528947  

24 1 756971  

24 30 799632  

6 16 418628  

9 28 439215  

11 14 720091  

9 2 909611  

16 2 152275  

8 4 356621  

9 28 77889  

20 26 487771  

29 22 372261  

25 11 107206  

8 26 648519  

4 5 436874  

18 19 967638  

17 13 826608  

18 6 149315  

19 10 591101  

16 3 89439  

10 31 633075  

25 26 933682  

2 17 550271  

14 24 101840  

1 28 92623  

29 12 319848  

3 28 456683  

22 12 745792  

16 28 391522  

18 12 631492  

6 19 359232  

29 5 614031  

14 10 241082  

7 4 33003  

1 5 261797  

12 19 974581  

6 15 513971  

15 13 235380  

11 19 31537  

21 27 433484  

6 30 984858  

16 27 469912  

26 8 505237  

15 12 675106  

5 12 421245  

20 21 519935  

7 24 558956  

14 5 343769  

4 13 552806  

10 2 876983  

20 8 593094  

10 21 186594  

5 15 850544  

6 30 734714  

11 3 474763  

18 22 32920  

13 27 110295  

19 9 760236  

7 10 305154  

14 19 666329  

16 8 306711  

14 15 836837  

6 17 387091  

5 23 714905  

15 31 369634  

3 16 613074  

11 26 419806  

9 13 336504  

11 20 82196  

26 2 721121  

9 15 686764  

28 26 963982  

3 1 539037  

26 3 433519  

14 18 322533  

2 18 627322  

12 29 384173  

14 6 152041  

23 15 307399  

10 7 370348  

20 26 886060  

13 18 626925  

13 26 271233  

13 26 630444  

28 23 875641  

15 2 250263  

12 6 561042  

15 24 208325  

27 29 454155  

2 1 937458  

16 19 591172  

22 31 725219  

2 10 914654  

5 22 53960  

7 4 547085  

6 29 742699  

11 6 798899  

4 2 825172  

30 8 752507  

30 28 178225  

15 9 490001  

14 7 945054  

23 30 671339  

14 15 28068  

30 21 776788  

31 27 292123  

8 4 884851  

30 7 202255  

17 3 973814  

6 31 199182  

8 14 15721  

29 28 590182  

21 17 79297  

14 30 138723  

26 28 230298  

9 25 443182  

20 1 767058  

3 31 860000  

18 14 687484  

10 19 68978  

10 16 895022  

4 13 508861  

21 7 277686  

19 15 590931  

14 13 197315  

5 1 95821  

6 24 395529  

3 23 897491  

16 20 889619  

2 18 80929  

23 25 804311  

11 29 634226  

19 18 543438  

8 3 107723  

22 14 418658  

11 19 689127  

17 22 726652  

25 24 140529  

21 6 241889  

23 5 928578  

17 28 755200  

26 7 126088  

16 24 400658  

11 31 377018  

27 11 918185  

14 29 55806  

4 11 588955  

25 10 19594  

28 31 372556  

2 4 806446  

27 31 560998  

31 26 466128  

23 5 914694  

22 18 987335  

9 11 994986  

4 24 691762  

15 25 631542  

19 16 711851  

11 10 550400  

24 11 801174  

21 4 839852  

11 4 488264  

17 26 570038  

1 15 28829  

6 23 576988  

20 25 578342  

30 8 587666  

18 27 149518  

16 4 41352  

9 27 706507  

6 14 709365  

2 25 434155  

21 8 273680  

14 8 292539  

22 12 916171  

9 29 62761  

17 27 304466  

18 14 713887  

1 27 826970  

25 5 532622  

26 10 637290  

28 9 734674  

5 29 774549  

3 12 704314  

17 31 994950  

18 9 157794  

9  

9588156  

8400960  

8982933  

1098823  

7323286  

3213171  

8275358  

185677  

5040140  

6 182  

6 3 150324  

5 3 409955  

4 5 322043  

3 2 423920  

6 5 293470  

3 2 474977  

2 6 63134  

6 1 161957  

2 4 953667  

5 3 361730  

1 3 88132  

6 5 5217  

2 5 434574  

6 5 276126  

6 4 312497  

1 4 848154  

1 4 843486  

1 2 450031  

4 6 206899  

5 3 406425  

2 1 411642  

1 5 873481  

3 6 628790  

5 3 342724  

3 2 152494  

4 1 124221  

6 1 49614  

2 1 938271  

4 6 96181  

2 5 137089  

6 1 979970  

5 6 800031  

2 4 620095  

3 1 487331  

5 2 231350  

2 1 843882  

4 3 874134  

6 3 623288  

4 5 495355  

1 3 510140  

4 2 677419  

6 1 485270  

6 5 342734  

4 3 654820  

2 4 100670  

3 6 974803  

2 1 598090  

1 6 995961  

3 2 402558  

6 2 418817  

1 6 571523  

2 6 646580  

4 1 273379  

4 1 564046  

3 2 804900  

4 2 721387  

2 3 966949  

1 3 68507  

2 3 665418  

3 2 288821  

6 3 86318  

3 6 419018  

2 4 712996  

3 6 196296  

2 6 264802  

6 5 658926  

6 3 613092  

5 1 255813  

1 5 362125  

4 2 65187  

4 5 56795  

5 2 286142  

5 6 482438  

4 5 263591  

6 5 226514  

2 1 478258  

5 6 352347  

6 5 151226  

6 3 36422  

1 5 340635  

1 2 120357  

3 4 585473  

1 6 568112  

6 4 747662  

6 3 470217  

6 5 335345  

5 1 846268  

5 6 260758  

2 3 194651  

1 3 581877  

2 3 963954  

6 4 41599  

6 4 714938  

3 1 132541  

3 6 720084  

1 3 615610  

3 5 22940  

3 6 2607  

5 4 52252  

6 4 442531  

2 5 953166  

6 4 919592  

6 2 568485  

2 6 804920  

3 4 815495  

3 4 287640  

4 5 851989  

1 5 184681  

5 1 993019  

5 4 754099  

6 3 976506  

2 5 916067  

5 4 571473  

5 2 386967  

4 5 224548  

3 1 581087  

1 4 989878  

3 4 841198  

3 6 162036  

6 2 48499  

6 5 713862  

5 1 570004  

4 3 564429  

4 2 463634  

2 5 880382  

1 6 720898  

3 6 602409  

6 2 852635  

5 3 808586  

4 6 34987  

3 5 237893  

1 2 389570  

1 6 596367  

2 4 222834  

5 1 73848  

4 3 22301  

1 5 960630  

4 5 256509  

4 3 230776  

3 5 253541  

3 5 506519  

2 3 329500  

5 6 33063  

2 3 193843  

2 1 618835  

2 5 95816  

5 1 194466  

2 1 825362  

5 6 705361  

5 6 938621  

4 2 22925  

1 2 387709  

1 3 753871  

5 2 207467  

4 3 472516  

6 1 183333  

5 1 8694  

4 2 632855  

3 5 571476  

6 1 110752  

6 2 14812  

4 3 768682  

6 2 492500  

2 3 314108  

1 2 865741  

2 4 309588  

4 5 458794  

6 4 546621  

3 2 657372  

3 4 49765  

2 4 825801  

2 5 500336  

6 3 617458  

1 4 180530  

2 3 785293  

6 2 792350  

2 1 782141  

3 4 602256  

4 1 172026  

5 2 458261  

5 3 562958  

5 4 232984  

1  

8078721  

27 198  

11 24 433879  

24 21 219171  

18 4 11521  

26 14 793661  

2 24 912268  

8 14 247036  

25 12 428609  

21 8 59896  

6 13 141010  

16 9 574888  

2 3 794058  

19 22 321930  

6 8 631943  

8 20 544210  

23 9 144855  

9 25 203760  

9 23 341974  

5 19 713172  

25 13 651900  

8 18 257756  

25 8 528781  

6 27 38321  

3 12 506953  

22 27 103808  

3 22 572526  

1 3 190159  

23 20 59561  

3 4 332974  

5 15 263749  

22 8 769410  

18 19 101833  

5 25 239834  

14 16 526128  

3 10 356632  

3 13 848342  

27 2 27459  

6 24 64902  

17 12 40927  

4 16 700700  

1 7 189563  

8 11 42349  

5 4 449808  

9 25 880570  

19 1 415140  

20 15 38586  

21 19 368543  

6 5 241708  

14 2 601486  

2 4 545191  

24 12 710648  

24 9 870462  

16 8 296631  

13 25 845521  

14 18 980539  

17 11 600931  

21 2 658095  

3 22 138645  

5 24 121785  

8 26 376926  

22 17 438549  

10 13 251531  

12 10 97052  

14 17 77590  

3 27 194873  

26 7 632558  

3 11 565221  

7 23 687006  

4 22 580283  

12 3 135237  

1 25 481885  

2 20 792725  

27 2 113237  

16 22 337243  

15 2 386024  

22 2 762112  

26 20 816261  

10 16 149956  

22 19 341090  

5 3 583959  

9 19 265376  

11 9 714675  

14 8 777378  

2 24 917670  

9 11 252834  

3 21 736907  

12 20 483317  

5 18 387571  

9 12 213487  

23 16 946278  

23 13 220436  

9 23 834947  

14 25 150213  

21 27 19541  

11 8 278675  

13 10 728803  

18 6 999243  

8 10 71162  

19 17 484170  

23 3 481136  

8 24 776181  

19 9 785901  

17 18 572997  

5 23 794115  

12 1 784417  

10 26 511626  

3 16 238503  

6 23 352950  

5 3 197236  

11 25 987800  

27 21 31503  

25 12 393800  

9 17 939014  

2 21 503767  

17 21 347195  

23 3 435777  

6 22 837210  

26 16 834685  

1 20 64836  

20 3 679782  

3 19 482363  

9 16 826265  

12 13 506854  

22 14 390770  

1 20 204106  

22 15 951143  

26 9 774566  

6 7 157266  

25 7 203108  

2 15 363559  

20 17 185161  

3 14 895039  

14 15 311797  

4 9 8431  

3 9 295408  

22 4 473496  

17 18 537968  

11 12 760030  

20 9 492632  

22 27 933008  

15 19 101663  

26 10 30097  

25 24 112111  

25 16 803070  

11 18 123091  

1 12 419370  

9 18 127683  

10 1 634296  

5 10 741188  

23 4 62252  

4 18 274724  

14 4 690627  

26 5 418326  

9 20 980457  

25 20 399827  

7 10 43861  

5 27 678156  

9 25 935696  

21 1 997947  

27 7 758864  

17 22 78409  

9 12 159162  

13 10 710556  

15 7 349145  

13 21 928292  

9 27 703448  

20 4 253682  

10 1 315330  

24 10 827835  

12 25 126902  

20 14 217044  

14 23 997812  

22 24 713257  

21 1 615860  

12 2 253511  

23 10 680298  

5 2 971925  

2 11 964126  

14 6 833556  

12 22 782720  

14 5 326645  

25 15 29730  

22 7 443371  

11 21 238859  

12 18 446287  

21 13 873514  

11 1 554422  

11 5 550659  

6 7 374730  

11 23 46008  

4 3 489211  

18 4 502309  

13 15 657903  

7 11 58107  

13 17 655805  

25 1 29502  

14 17 370449  

7 2 871001  

14 7 205109  

2  

2411556  

2838287  

29 329  

29 14 211984  

8 22 881424  

12 28 594862  

18 28 605808  

11 13 110912  

5 28 565745  

19 18 967138  

10 3 365761  

5 16 189142  

1 6 574883  

4 26 449834  

12 5 343445  

1 8 411311  

8 17 537284  

8 27 835413  

4 24 163043  

16 13 861121  

16 14 946551  

1 18 720738  

13 19 365915  

19 20 900659  

15 19 499282  

22 28 209119  

1 15 524764  

27 6 951319  

21 3 459971  

25 9 452112  

9 18 810013  

27 5 357056  

8 18 478980  

13 7 567090  

29 13 514996  

8 26 874212  

24 26 770712  

10 16 535327  

28 7 946633  

25 24 251762  

7 3 503442  

11 21 992211  

27 20 846895  

19 24 543484  

2 23 378338  

3 23 999214  

24 17 527999  

1 18 358642  

12 16 116036  

26 3 300132  

4 10 480710  

19 12 317825  

10 1 6072  

10 19 728907  

16 13 386990  

27 15 28657  

6 9 313971  

2 9 833103  

7 1 500839  

10 5 802943  

19 11 608489  

22 21 922597  

4 3 500114  

11 15 403455  

1 22 432111  

27 22 262433  

28 23 611887  

11 14 632905  

3 14 486947  

7 10 787583  

9 3 442044  

1 26 747320  

22 21 446677  

14 21 28216  

6 14 79270  

28 18 256710  

13 21 468233  

18 2 313523  

2 20 125414  

3 20 868265  

5 3 376251  

22 8 171795  

5 7 983805  

7 20 199268  

29 18 363194  

20 8 822255  

29 20 376851  

12 8 564351  

26 1 755149  

17 4 217178  

17 29 153955  

9 14 321699  

23 18 452471  

1 16 15470  

20 8 591441  

24 19 121289  

17 10 990817  

1 21 69028  

7 9 693060  

3 26 68400  

19 5 459968  

29 14 120689  

9 28 321677  

24 28 220240  

21 10 328243  

7 5 241307  

28 13 732494  

3 13 786387  

5 19 716510  

16 21 164627  

14 2 482650  

12 22 563182  

29 13 735659  

27 20 510063  

29 4 359555  

25 28 330335  

8 3 324636  

12 27 387965  

1 2 660704  

13 15 1843  

7 12 319301  

20 13 757447  

5 13 33622  

12 2 46388  

11 1 871044  

16 25 969711  

12 24 800871  

9 6 418418  

11 27 268825  

13 11 283859  

7 9 297894  

12 20 875110  

1 24 63047  

3 7 343703  

24 17 800097  

12 4 544875  

26 7 575261  

14 15 84507  

20 18 26235  

19 1 451353  

4 7 659819  

29 10 420006  

1 2 257693  

13 5 392188  

27 28 366257  

5 2 506749  

3 16 366797  

9 10 586312  

26 2 591003  

18 24 879553  

16 18 982347  

25 2 960251  

19 9 517554  

1 13 61049  

26 15 84149  

24 5 293555  

11 29 543364  

12 6 108343  

13 1 891255  

12 17 34226  

28 18 510828  

17 26 28381  

10 11 963291  

23 18 599301  

29 13 513991  

25 2 282620  

24 21 989694  

21 7 661449  

21 2 265588  

22 24 261903  

2 25 733607  

27 1 487535  

1 19 124047  

18 12 757670  

23 13 503158  

16 24 243659  

7 18 565484  

13 16 575987  

7 13 638369  

19 5 251328  

22 27 891467  

21 24 43634  

21 16 191795  

6 26 939256  

11 19 200708  

11 5 744778  

26 12 794894  

3 16 506458  

29 22 999961  

10 4 471745  

5 25 646712  

25 16 552369  

8 28 394661  

9 25 473288  

6 27 106688  

23 29 488614  

5 25 807125  

18 27 874975  

24 19 945230  

14 20 67661  

28 24 536874  

3 12 570125  

1 11 654946  

6 12 948089  

8 17 690869  

19 10 935501  

23 7 552959  

18 25 498188  

23 15 82200  

13 1 619073  

7 4 189197  

28 15 360495  

5 26 308583  

4 13 515803  

3 12 191615  

20 28 615539  

18 13 194529  

5 9 928546  

15 25 547248  

29 19 358698  

17 8 413003  

29 19 816851  

13 21 575206  

23 3 495192  

19 20 484489  

3 24 488324  

1 5 574359  

4 16 279466  

21 22 690121  

28 13 977623  

11 29 90058  

17 28 718296  

8 3 830541  

2 17 803376  

24 7 347224  

29 1 811559  

5 23 259317  

29 26 308971  

4 17 769973  

4 15 903581  

14 17 424539  

2 5 343900  

1 4 627020  

20 6 465513  

4 21 474918  

8 20 849763  

28 16 551296  

15 8 901555  

17 3 922257  

3 6 644297  

1 11 975430  

19 13 779601  

14 5 422716  

13 21 800836  

4 17 575806  

15 5 678686  

23 15 40882  

1 29 228400  

3 22 185890  

1 21 530608  

11 8 816216  

15 20 962075  

19 28 251305  

5 3 6047  

24 7 235707  

8 29 59766  

6 13 554530  

1 26 740419  

22 10 787378  

24 9 119945  

10 21 598371  

20 19 366027  

17 21 372073  

3 19 607780  

7 3 439260  

6 8 417810  

19 6 444982  

20 6 475738  

16 27 638021  

7 13 423612  

19 22 644816  

12 5 691644  

17 13 76781  

9 7 214108  

4 9 162290  

4 26 410763  

9 18 730117  

6 7 306241  

24 26 669742  

7 25 669539  

21 14 267706  

25 22 748251  

29 5 600868  

15 18 386866  

23 27 472059  

19 25 89326  

7 5 812680  

6 29 908252  

2 1 762698  

26 4 870792  

11 18 518733  

24 19 738996  

28 20 594815  

25 5 690580  

26 19 981338  

1 8 682858  

5 7 630846  

14 12 401426  

17 5 841747  

6 2 951606  

27 4 361874  

15 27 4040  

1 17 279778  

14 12 133131  

6 1 980109  

25 1 654527  

1 27 984241  

19 11 207434  

19 28 782070  

20 25 73371  

15 22 575024  

28 7 21415  

21 29 191006  

5 13 625422  

15 10 195177  

14 5 888681  

12 6 795258  

17 16 243939  

24 5 175680  

7 16 836826  

12 2 130873  

28 29 543848  

2  

7040077  

9847451  

19 217  

8 5 443438  

2 18 449967  

19 7 111022  

15 14 272670  

1 4 517876  

8 17 871054  

10 12 1926  

13 5 545773  

12 18 909577  

12 16 62427  

15 12 466290  

12 15 93663  

4 10 366333  

8 13 524436  

11 6 866393  

5 19 949223  

14 16 897005  

15 12 698448  

13 18 60909  

9 12 126163  

2 5 573033  

12 16 322903  

13 19 138327  

5 4 812299  

13 11 520499  

9 16 583399  

12 10 164577  

8 2 807879  

4 3 419678  

3 7 992710  

11 19 315613  

4 16 970291  

8 19 298942  

1 8 819440  

7 4 919190  

18 10 600118  

3 11 924348  

17 3 801456  

8 4 326573  

12 6 647340  

11 17 819520  

4 2 520790  

3 1 527250  

10 14 705291  

10 2 487784  

16 17 320789  

5 8 353697  

4 13 196472  

7 1 458925  

9 11 714088  

6 18 317566  

3 2 891335  

4 2 280397  

3 8 488898  

8 15 649293  

8 11 926157  

10 12 127368  

6 13 646387  

10 19 491978  

2 9 984909  

7 11 694997  

15 13 467936  

16 14 4341  

4 5 762387  

18 14 8217  

7 1 91186  

18 8 198953  

6 3 268865  

1 10 755631  

13 16 730763  

5 9 198698  

1 19 719390  

5 2 481777  

19 15 489993  

6 13 97530  

18 5 625381  

6 3 302721  

10 5 588475  

19 5 713081  

16 15 477753  

3 19 290177  

16 1 914399  

8 5 940458  

19 10 539235  

12 8 451504  

16 19 733939  

11 1 541653  

7 3 254733  

1 17 248837  

3 16 539013  

15 13 969763  

17 11 358133  

18 6 203166  

16 13 980438  

10 9 714376  

6 5 148991  

6 19 553147  

8 19 682473  

2 4 784083  

7 8 579959  

4 16 454444  

18 2 173961  

17 13 832039  

7 3 546414  

12 4 211757  

15 4 764903  

12 18 166930  

3 13 777126  

9 17 873436  

9 10 844231  

8 11 18191  

8 14 154914  

2 14 350311  

4 18 399084  

10 7 882410  

6 7 846136  

4 7 77592  

16 18 365724  

11 5 906198  

1 6 717775  

9 10 779466  

19 12 29950  

14 2 992957  

9 16 210802  

12 6 218398  

15 11 321739  

10 15 592009  

7 8 639404  

10 18 76586  

3 19 357999  

18 8 690307  

3 7 661175  

8 17 982354  

16 6 218968  

6 17 359470  

18 12 418447  

17 2 573925  

19 6 947780  

16 15 43726  

10 18 17567  

14 12 318985  

4 15 173202  

16 1 908521  

18 15 267991  

16 7 202789  

13 6 776713  

9 11 724492  

2 3 768217  

13 17 950305  

11 10 988872  

19 2 612982  

13 5 460091  

14 18 40703  

12 16 15534  

17 13 960412  

12 3 780947  

17 9 943990  

14 7 863874  

3 19 279371  

19 7 228786  

5 3 13538  

7 16 932289  

4 7 374772  

14 18 359760  

1 12 706182  

10 4 522002  

5 17 507193  

7 12 66538  

11 14 132348  

7 14 107604  

6 1 129794  

2 9 128426  

9 14 684113  

4 13 255333  

16 5 303316  

3 14 658791  

9 3 725328  

15 6 440877  

18 17 548481  

4 17 194626  

6 3 839404  

11 17 523516  

14 7 778848  

7 12 598515  

4 8 730759  

14 19 668625  

16 15 759634  

9 7 315862  

8 5 566093  

18 8 40216  

7 10 186873  

6 1 864482  

16 12 949154  

15 18 147071  

6 18 496586  

2 12 988540  

19 5 722173  

2 13 376243  

6 7 64092  

10 15 462919  

1 6 701149  

17 7 979246  

9 17 36190  

5 1 691648  

3 7 594216  

12 10 165408  

16 5 12586  

7 6 691976  

2 8 453811  

17 18 772213  

14 15 277487  

15 12 647242  

13 18 966150  

2 3 948481  

16 2 427398  

8 13 411205  

16 7 117185  

1  

5000093  

28 328  

25 22 74538  

27 14 363102  

8 3 640588  

2 10 287829  

25 6 770331  

1 28 718811  

25 19 662560  

9 14 73765  

20 6 707301  

28 11 876648  

15 7 920965  

5 18 888838  

2 25 439380  

14 10 357510  

22 6 71711  

12 7 266067  

3 15 199089  

2 7 358826  

24 18 738725  

12 25 322270  

28 14 727460  

1 22 683191  

14 4 557052  

20 9 628763  

15 27 894829  

17 14 610269  

3 20 485446  

28 18 740801  

18 14 376427  

19 9 64663  

28 8 665132  

11 9 302121  

26 6 324  

25 9 147733  

27 24 146291  

19 24 456376  

27 10 838180  

9 22 386301  

13 11 189498  

19 13 924555  

21 24 342790  

8 7 107682  

1 16 490592  

24 12 50708  

12 11 150255  

27 13 353915  

10 24 405280  

13 4 605357  

17 28 995155  

15 1 396915  

11 18 358699  

1 12 138955  

16 11 919534  

27 2 847846  

21 1 438800  

6 23 486129  

13 10 887990  

16 3 676150  

27 5 170160  

17 20 588724  

12 2 866430  

14 2 251817  

12 1 644147  

5 27 87184  

22 4 196828  

9 21 176738  

18 5 561928  

11 4 552474  

4 2 54526  

4 19 16205  

15 14 880686  

28 11 215547  

24 22 461367  

2 26 488778  

22 20 710873  

13 12 527093  

11 1 417141  

18 11 459132  

11 27 70393  

8 2 351187  

9 28 214780  

10 12 536222  

25 7 970819  

23 21 921753  

20 26 753220  

20 22 904019  

24 4 892984  

20 5 91750  

3 15 692820  

28 7 382705  

14 15 750129  

14 8 694224  

7 16 983158  

6 11 744726  

2 14 615167  

1 18 274957  

23 13 417184  

18 17 636481  

8 3 968967  

23 2 469169  

24 16 185995  

8 13 483779  

14 16 206372  

24 22 746869  

10 24 40585  

11 20 238320  

23 4 845389  

11 20 544208  

26 18 419495  

27 11 193838  

26 13 234661  

10 11 486059  

14 4 186432  

7 9 346277  

3 13 160559  

6 24 162946  

9 25 787892  

12 16 961689  

4 8 22299  

13 20 256959  

7 3 743017  

3 11 979983  

18 26 196229  

26 23 39627  

11 13 268781  

6 26 333577  

14 6 870497  

2 10 848506  

27 25 253125  

18 22 270348  

20 28 900306  

5 2 721064  

3 19 760958  

19 1 630776  

10 23 177504  

6 12 403530  

22 26 901095  

6 11 876700  

15 9 49677  

19 10 549110  

27 14 509193  

8 18 619042  

12 4 355904  

13 22 911192  

20 3 550  

11 20 126998  

12 14 122591  

6 3 396297  

6 2 743873  

14 20 187619  

15 2 500844  

15 22 942917  

28 5 977468  

3 1 833429  

19 4 517724  

12 26 331835  

5 10 609340  

7 27 220735  

19 4 14524  

8 1 760183  

22 15 728061  

21 13 334814  

21 12 817858  

8 15 938150  

16 17 842817  

11 28 709362  

26 17 457667  

9 7 505178  

23 10 244945  

22 17 726646  

25 10 532092  

17 14 654125  

14 18 744488  

27 25 126382  

14 24 907527  

26 21 406848  

26 12 548212  

4 17 910311  

13 21 286932  

13 26 940088  

6 18 837656  

19 6 586389  

8 5 152979  

16 3 174070  

12 28 554329  

2 9 127598  

17 6 674885  

12 22 243701  

14 18 57461  

22 3 114219  

25 8 219420  

1 27 495097  

17 18 515261  

16 18 661807  

9 1 101111  

26 14 170115  

19 2 117793  

23 25 711382  

15 11 116331  

11 16 672877  

5 12 534605  

28 24 267403  

12 13 210620  

1 12 487237  

3 20 353645  

5 17 750074  

16 19 599723  

16 13 934452  

9 11 180922  

19 6 626065  

4 10 242672  

8 22 868400  

10 5 605988  

13 17 608415  

18 20 566102  

10 8 549731  

28 7 686897  

2 22 168838  

17 14 755604  

10 5 21009  

18 20 595623  

10 11 215216  

9 4 374884  

20 16 589889  

14 17 554740  

11 27 854195  

25 10 174722  

2 23 150463  

19 24 492801  

2 5 350769  

19 23 397244  

1 16 166830  

16 24 443281  

7 15 437216  

27 12 635873  

10 22 909247  

1 19 523764  

26 4 79146  

28 6 26197  

28 7 62190  

4 9 296836  

23 21 5511  

12 8 572966  

4 15 572484  

24 13 161535  

16 23 873516  

6 7 774510  

17 16 67765  

22 27 438470  

7 27 609525  

24 14 667345  

7 9 691202  

17 20 412661  

22 8 722959  

25 15 695632  

11 2 918122  

2 7 244624  

12 7 333507  

24 12 851585  

14 18 808011  

10 13 37201  

10 3 969101  

19 3 737836  

7 6 753684  

21 5 414866  

28 12 359265  

11 18 692771  

18 2 60708  

3 19 868718  

24 16 905918  

6 2 875018  

24 5 129206  

15 12 464948  

21 28 148633  

9 25 533462  

15 8 463646  

3 2 725395  

14 20 765828  

5 22 509203  

14 18 458318  

12 23 445511  

5 2 308631  

26 1 425787  

26 5 812978  

18 13 131386  

15 27 915710  

24 14 475155  

7 27 252102  

18 15 61992  

4 12 911549  

17 23 925787  

4 12 437272  

22 9 740288  

8 18 786668  

21 7 772933  

3 22 846427  

16 1 850064  

18 7 509318  

8 9 368544  

19 24 812812  

19 25 264390  

25 28 598297  

16 5 976442  

20 13 863771  

15 5 408918  

23 19 178047  

26 6 118451  

1 8 988230  

27 15 36858  

26 5 289889  

9 7 721993  

27 15 295032  

11 14 801285  

4 5 699241  

27 20 801877  

16 26 756932  

22 23 963761  

28 8 446576  

13 6 424774  

6 15 509402  

7 8 95656  

3 18 625674  

27 28 53080  

11 16 118160  

19 14 607583  

3 13 326985  

18 6 90087  

23 17 296010  

6  

3235673  

5937718  

1415411  

5867970  

7383757  

9924812  

29 89  

2 22 940702  

18 5 430645  

14 26 409560  

24 25 224865  

4 28 834533  

17 25 900258  

2 11 56843  

25 21 292516  

17 10 676838  

8 29 983347  

4 22 450386  

8 10 405691  

17 22 244507  

4 13 734877  

2 13 35880  

18 5 459673  

20 7 179475  

4 7 353348  

13 1 910978  

4 25 948248  

25 20 442571  

27 11 367539  

13 19 218418  

2 26 86682  

6 10 50741  

11 16 614418  

9 26 801056  

16 14 477010  

8 2 632499  

3 21 255289  

14 11 56928  

15 26 156976  

28 10 967488  

12 26 745798  

22 4 876568  

22 29 677623  

8 6 670984  

19 6 640095  

21 7 385038  

17 11 78593  

26 17 431239  

13 20 511560  

23 4 779228  

3 25 930068  

1 25 317429  

4 2 335936  

4 24 482893  

1 8 168165  

29 21 275644  

5 8 56449  

8 5 804742  

19 9 757663  

17 23 511942  

27 26 498981  

21 18 408183  

19 21 798384  

16 17 81199  

2 9 520461  

29 9 605207  

14 29 701747  

10 15 973704  

10 29 789924  

4 8 385372  

21 4 910887  

9 3 270182  

21 17 481765  

29 3 176240  

9 18 38880  

9 16 177162  

13 1 888245  

25 2 404070  

18 12 193909  

28 7 495689  

13 9 69233  

7 9 210981  

15 17 411261  

18 17 398760  

27 17 1512  

14 22 497995  

6 17 696225  

28 27 868157  

2 7 346365  

6 5 262459  

6 2 800554  

7 4 862328  

15 5 45330  

23 14 870020  

11 23 941605  

24 15 476661  

1  

3810686  

40 0  

1  

0  

40 39  

1 2 1  

2 3 2  

3 4 3  

4 5 4  

5 6 5  

6 7 6  

7 8 7  

8 9 8  

9 10 9  

10 11 10  

11 12 11  

12 13 12  

13 14 13  

14 15 14  

15 16 15  

16 17 16  

17 18 17  

18 19 18  

19 20 19  

20 21 20  

21 22 21  

22 23 22  

23 24 23  

24 25 24  

25 26 25  

26 27 26  

27 28 27  

28 29 28  

29 30 29  

30 31 30  

31 32 31  

32 33 32  

33 34 33  

34 35 34  

35 36 35  

36 37 36  

37 38 37  

38 39 38  

39 40 39  

1  

20  

6 9  

1 2 1  

1 3 7  

2 3 1  

2 4 3  

2 5 2  

3 5 4  

4 5 1  

4 6 6  

5 6 2  

1  

6  

样例输出

276  

276  

276  

248  

66  

437  

374  

420  

0  

212  

0  

345  

0  

0  

0  

0  

0  

55  

175  

0  

0  

27  

0  

27  

27  

147  

385  

780  

590  

12  

数据范围与提示