미리 하는 경고 (라지)

시간 제한5초메모리 제한512 MB

요약

과거 사건 시각이 주어질 때 모든 시각에 같은 시간을 더해 최대공약수가 가장 커지는 최소 대기 시간을 구합니다.

난이도: 보통10점 중 4점
유형: 정수론
정답자: 아직 제출이 없습니다

문제

우리 행성 잼코드 IX에서 세 번의 대사건이 일어났다. 각각 26000, 11000, 6000 슬라보초 전의 일이다. 4000 슬라보초 뒤에는 각 사건 이후 흐른 시간이 모두 5000 슬라보초의 배수가 된다. 가능한 가장 큰 값이다. 그리고 종말이 온다.

당신은 운 좋게도 잼코드 X에 산다. 잼코드 IX의 종말은 채 한 해도 지나지 않은 일이다. 그런데 잼코드 X에도 불길한 예언이 전해진다. "심판의 순간이 지난 뒤, $N$ 번의 대사건이 맞는 첫 번째 최적 기념일에 종말이 온다. 64비트로는 너를 구할 수 없다. 미리 경고했다."

잼코드 X 사람들은 이 예언을 걱정한다. 대사건은 이미 모두 일어났고 각각의 시각도 슬라보초 단위까지 측정해 두었지만, 최적 기념일이 언제인지는 아무도 모른다. 잼코드 IX 과학자가 남긴 일지를 연구한 끝에 다음 이론이 나왔다.

심판의 순간은 바로 지금, 당신이 이 문제를 푸는 순간이다. 지금부터 $y \ge 0$ 슬라보초가 지난 어느 시점에, 각 대사건 이후 흐른 시간이 모두 어떤 최대의 수 $T$ 로 나누어떨어진다. 이 가장 큰 $T$ 를 만드는 가장 작은 $y$ 가 종말이 오는 최적 기념일이다.

잼코드 IX를 예로 들면 대사건은 세 번이었고 심판의 순간보다 각각 26000, 11000, 6000 슬라보초 전에 일어났다. 4000 슬라보초가 지나자 각 사건 이후 흐른 시간이 모두 $T = 5000$ 슬라보초의 배수가 되었고, 종말이 왔다.

종말까지 남은 시간을 구하라. 예언을 잊지 마라. 잼코드 X 사람들이 두 해 동안 문제를 풀며 64비트 정수로 늘 충분했다고 해도, 지금도 앞으로도 충분하다는 보장은 없다.

입력

첫 줄에 테스트 케이스의 수 $C$ 가 주어진다. 이어서 $C$ 개의 줄이 주어진다. 각 줄은 정수 $N$ 으로 시작하고, 공백 하나를 둔 다음 $N$ 개의 정수 $t_i$ 가 공백으로 구분되어 주어진다. $t_i$ 는 $i$ 번째 대사건이 일어난 뒤 흐른 슬라보초 수이다.

제한

$1 \le C \le 100$
$2 \le N \le 1000$
$1 \le t_i \le 10^{50}$
$t_i \ne t_j$ 인 $i$ , $j$ 가 적어도 한 쌍 있다.

출력

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$ 는 1부터 시작하는 테스트 케이스 번호이고, $y$ 는 모든 $i$ 에 대해 $t_i + y$ 가 가능한 가장 큰 정수 인수 $T$ 의 배수가 되게 하는 최소의 슬라보초 수이다.

힌트

잼코드 계 주민들에게는 다행스럽게도, "종말"은 "거대한 잔치"를 잘못 옮긴 말로 밝혀졌다. 잼코드 IX의 누구도 이 사실을 알려 주지 않았는데, 잔치가 너무 즐거웠기 때문이다.

예제2

예제 1

입력

3
3 26000000 11000000 6000000
3 1 10 11
2 800000000000000000001 900000000000000000001

예상 출력

Case #1: 4000000
Case #2: 0
Case #3: 99999999999999999999

예제 2

입력

100
8 30630665731 427849977936 353814895985 203045069959 543380122712 893456019592 173813766724 627734511613
12 30370228717167 30370228717177 30370228717257 30370228717277 30370228717377 30370228717237 30370228717267 30370228717617 30370228717317 30370228717607 30370228717527 30370228717587
12 3404199849583952079322133066643923034831 3404199849619253713730802759986876817765 3404199851101922358894929880390935700993 3404199852619892638467726694137948367155 3404199851172525627712269267076843266861 3404199852302177928789699454051364320749 3404199851349033799755617733791612181531 3404199851384335434164287427134565964465 3404199851031319090077590493705028135125 3404199852902305713737084240881578630627 3404199850960715821260251107019120569257 3404199853114115520189102400939301328231
4 658609024395 534980095940 482187204567 889396453294
9 186984026622107 186984026622113 186984026622209 186984026622137 186984026622143 186984026622383 186984026622251 186984026622269 186984026622359
9 5925978210433966178030467185734480057619 5925978210710828641436561985502990797498 5925978219016702543619405978558312993868 5925978223169639494710827975085974092053 5925978235628450347985093964668957386608 5925978217909252689995026779484270034352 5925978228983751226238818770224699629512 5925978223723364421523017574622995571811 5925978213202590812091415183419587456409
6 867115495644 584375195555 108302620830 10408744097 28964707664 613052297864
8 650041863497189 650041863497201 650041863497381 650041863497717 650041863497513 650041863497561 650041863497345 650041863497513
7 4401148418708053446209570654235756770206 4401148419405493593368615526974545811157 4401148461949342570070352764040677309168 4401148473108384924615070727861301964384 4401148438236377566662827090921849916834 4401148459857022128593218145824310186315 4401148451487740362684679672958841694903
12 121533112184 599285936563 166187204082 29472940782 992246552704 974575188765 201246970640 562853479287 143731801893 245704888446 405112458251 158092096498
7 518218744629698 518218744629700 518218744629700 518218744629734 518218744629732 518218744629728 518218744629786
7 1406406560720374493316184367551193489239 1406406560931777312581303866222495937105 1406406564737028059353454842305939998693 1406406562622999866702259855592915520033 1406406576152780299669907770556272183457 1406406570656306998776800805102408538941 1406406563257208324497618351606822863631
2 484254526116 205565208349
6 782380691492859 782380691492869 782380691492979 782380691493199 782380691493219 782380691493139
8 9609772465276339957459365272030366709667 9609772465393429198597919223916992231669 9609772471247891255525616818248268331769 9609772475814371659929220941826663689847 9609772476985264071314760460692918909867 9609772466095964645429242935236745363681 9609772476868174830176206508806293387865 9609772469842820361862969395608762067745
8 467642442014 949978376106 836456883930 278164413948 145000509337 863365270001 716882964174 45088017400
7 451059862848511 451059862848521 451059862848601 451059862848711 451059862848781 451059862848941 451059862848651
12 7472925120870397517431003374537590994771 7472925120988738372230231609341723335403 7472925124065600597010165714249164191835 7472925131994437868558457446126031014179 7472925125012327435403991592682222916891 7472925131166051884963859802497104629755 7472925125367349999801676297094619938787 7472925121698783501025601018166517379195 7472925131994437868558457446126031014179 7472925123473896323014024540228502488675 7472925127615826240987012758373134410795 7472925122053806065423285722578914401091
9 792110533605 786580129161 78679432064 102789757263 141687286481 118769613389 245865625003 674912931207 8060719693
7 651330745014259 651330745014271 651330745014571 651330745014559 651330745014367 651330745014763 651330745014739
10 5674612098074644965481554181184019449843 5674612098729344988033614544724142771336 5674612101348145078241855998884636057308 5674612110513945393970701088446362558210 5674612136047246273501055266511172096437 5674612114442145529283063269687102487168 5674612123607945845011908359248828988070 5674612119679745709699546178008089059112 5674612120334445732251606541548212380605 5674612115096845551835123633227225808661
12 478617533621 551089215792 262032058642 477915203437 135949026614 517883131261 827527562170 493155480775 369464908904 721614022889 297428920652 404749080352
9 355438835635763 355438835635773 355438835636073 355438835635973 355438835635843 355438835635873 355438835636183 355438835635813 355438835636163
12 315033990112414400049582703453728686369 315033990494485962073549182363575862642 315033993551058458265281013642353272826 315034026409212792326398199889210432304 315034008451849377199973691126393147473 315033995843487830409079887101436330464 315033998517988764576845239470366564375 315034003102847508864442986388532679651 315034015711209055655336790413489496660 315033996225559392433046366011283506737 315034017621566865775169184962725378025 315034023352640296134666368610433022120
4 949578174531 189505797744 580987713514 701317971051
2 92946585102678 92946585103678
9 4838979529217842282955865175293291598630 4838979530158751074365081553056470946921 4838979583790552184690415085557693799508 4838979562149649982278438397004568788815 4838979576263281853416684063452259013180 4838979564972376356506087530294106833688 4838979606372363178511608151873998158492 4838979536745112614229596197398726384958 4838979592258731307373362485426307934127
5 912857108203 270525763548 214360872186 782340102566 237761366021
7 5355675684245 5355675684251 5355675684317 5355675684311 5355675684413 5355675684425 5355675684527
4 4793142490571557580146838348738640024433 4793142490877776380724238910784299245673 4793142514150405224606681626254400059913 4793142504045184805552463078747645758993
8 602800868702 892891024842 502635133273 374609229431 385850589373 957011413417 287239937853 695729255666
8 510449278902155 510449279902138 510449286902019 510449297901832 510449307901662 510449308901645 510449309901628 510449298901815
12 9495969588905863339565413101832720158646 9495969589021086357208250983624715906785 9495969591325546710065008619464630869565 9495969598815042856849470935944354498600 9495969598930265874492308817736350246739 9495969596049690433421361772936456543264 9495969594897460256992982955016499061874 9495969598469373803920957290568367254183 9495969599736826997992173990280320483712 9495969596280136468707037536520448039542 9495969600428165103849201281032294972546 9495969592592999904136225319176584099094
11 67897318576 654365946101 975424429181 400017223392 548823069750 256896610382 660440339058 302538878963 463442477408 130972382457 801431958209
3 293495282271822 293495282272822 293495282305822
8 9010705347957921805187922539986211860747 9010705348325811721881024789340056654624 9010705372974436140318875496047657844383 9010705368559757140001648503801520317859 9010705384746913474498147475370691248447 9010705379964344557487818233770708928046 9010705382907463891032636228601467279062 9010705352372600805505149532232349387271
2 731843641258 7735525300
3 43244319073227 43244319074227 43244319086227
7 3798871675260856696618778398244031095678 3798871675418637321465571367686865406826 3798871685832158561353907350913929942594 3798871681572081690490497175957403541598 3798871689145551683136559709213450476702 3798871685358816686813528442585427009150 3798871676838662945086708092672374207158
6 246879325020 457423721884 114677687625 670652282253 379435087150 300263955745
6 132258601327733 132258601328733 132258601338733 132258601360733 132258601349733 132258601353733
4 2714164844103208736604557126183019870538 2714164844184221615700527232593057543276 2714164851151329217953956383856297398744 2714164848801955724170823297965204889342
6 515753259783 819065899686 992391350628 911196274133 837834937926 539642501388
4 926406297047711 926406297048711 926406297073711 926406297050711
10 7669754072386642595767214598837443080721 7669754072450884749441744565167276120773 7669754073350274900885164093784938681501 7669754074442391513352173521392100362385 7669754077204804121356962073574921084621 7669754073671485669257813925434103881761 7669754074699360128050293386711432522593 7669754075727234586842772847988761163425 7669754075084813050097473184690430762905 7669754076369656123588072511287091563945
8 37601935673 501003416752 680160315096 904105647608 2907546344 109883814088 447401085 47293831004
6 970500479113518 970500479113520 970500479113570 970500479113576 970500479113540 970500479113548
3 4539404347710581469256732115813083745110 4539404348660855183094222083953377615303 4539404432284942000793339280299238192287
5 18781112920 325853379467 146992773212 603978806102 377358760245
12 941069478311062 941069478311072 941069478311402 941069478311202 941069478311142 941069478311082 941069478311242 941069478311462 941069478311452 941069478311522 941069478311122 941069478311122
2 7925709350467576089399818599734930198494 7925709350646432461916365802030084265576
9 59349969953 153477172548 701392098861 518828180387 782772879036 404196803583 200882892032 735912985046 870118394412
9 305209042462543 305209042463543 305209042481543 305209042504543 305209042495543 305209042489543 305209042492543 305209042463543 305209042485543
3 8902986716376349537115719291533122491809 8902986717075855810388326545537978725137 8902986761844257299835190801848777658129
3 624296169606 48667166366 52008014409
4 534621132548241 534621132548243 534621132548269 534621132548283
12 1223824172111727184946996623196630006869 1223824172533116978380794680630605245948 1223824173797286358682188852932530963185 1223824188967318922298918920555639570029 1223824187703149541997524748253713852792 1223824207508469833386033447650550089505 1223824180960912847056755829310110027528 1223824200766233138445264528706946264241 1223824210879588180856417907122352002137 1223824202873182105614254815876822459636 1223824209615418800555023734820426284900 1223824186017590368262332518517812896476
6 824547059746 68396480132 440224950148 660091985875 827606185557 799833047389
5 724791293052660 724791293052666 724791293052876 724791293052834 724791293052864
3 4678439523507614635029667475665639245654 4678439524090583417044676110182829326134 4678439549741209825705056028939192867254
11 692663130113 72324216903 25027731027 135799151535 870096972042 692477436050 930481011362 75241163841 43370024364 703272640079 776596754115
2 169216627472968 169216627472978
4 4422336917587866359989122896295489546550 4422336917921489776358852407957898206546 4422336934936284011215057502740739866342 4422336930599179598408573851129427286394
8 904779982999 523840162329 282993863732 950406072149 358683277625 659237666431 268622310685 270584642116
11 459729182182175 459729182182181 459729182182409 459729182182229 459729182182355 459729182182187 459729182182445 459729182182355 459729182182391 459729182182265 459729182182385
2 5700779833378832920826489470509845782021 5700779833642359110511191385742405301268
11 331943473044 642457875198 269644289937 5250047177 210807273395 200139064126 833522462009 540028612325 962401995927 403506997821 991511374235
3 376263823614347 376263823614349 376263823614351
4 9471487911915389123495160220421430931375 9471487912378786349748982622651634195219 9471487948523769997547129996607488775051 9471487929987880947394233907399358221291
11 77415271556 434761214372 135366714281 24098661380 457567502855 188386752796 562604816305 650237066430 306242824421 669836412235 144993823300
7 940747354011216 940747354011222 940747354011468 940747354011342 940747354011324 940747354011270 940747354011384
5 7356261124481785628790763213195308384229 7356261125064495181418356276948106206175 7356261181004612233667290397216697112991 7356261131474300260321879978228882247581 7356261164688744760094684612138358098503
10 656626498138 70687192779 865883503726 506029717999 591702072871 423062750586 775905858569 582912838025 518025108991 143802151518
12 778137234176086 778137234177086 778137234215086 778137234187086 778137234215086 778137234212086 778137234208086 778137234184086 778137234184086 778137234179086 778137234176086 778137234226086
4 5871000454819887997303013105192745041886 5871000455341890762306393860427127789794 5871000462649929472353724433708486260506 5871000468391959887390912741286696487494
10 451297008818 588541145497 353516922804 451646620217 251293181089 110702406618 266932620753 579775394964 804583654253 986908593736
4 215774689141936 215774689141942 215774689142212 215774689142086
11 3986135104810711873549315067970101768026 3986135105226552705834352148586504924315 3986135122276026829520872453859034332164 3986135104810711873549315067970101768026 3986135106474075202689463390435714393182 3986135118949300171240575808927809081852 3986135119780981835810649970160615394430 3986135119365141003525612889544212238141 3986135129761161810651539904954291145366 3986135121028504332665761212009824863297 3986135135998774294927096114200338489701
12 722615088299 371615147340 817718779628 101409642228 658098235583 363994903091 490737860026 546971543562 517805182110 539828386695 54171012233 579135305040
2 992251313970679 992251313970681
7 4969087699757511262606550650668854869690 4969087700640990408917211901292953106855 4969087735980156261343661926256882593455 4969087713009698457266469410030328427165 4969087759834093211731515693107534996910 4969087717427094188819775663150819612990 4969087732446239676101016923760489644795
7 657708233121 159551424251 589193000383 768818669149 292538412560 779215285300 38474271234
12 862399674668441 862399674668447 862399674668537 862399674668687 862399674668537 862399674668561 862399674668681 862399674668609 862399674668729 862399674668687 862399674668711 862399674668651
3 4166228242666017356279304086822555012435 4166228243544018497143802530657728583284 4166228327832128020135653138834391384788
7 436525978291 669296039281 27348227640 111856171391 380554752794 81936673212 918038795822
8 545373750927524 545373750927527 545373750927644 545373750927572 545373750927572 545373750927641 545373750927623 545373750927536
5 61996524949105188709407690433743930244 61996525411929852331013111659828861294 61996559660954960329814282390113758994 61996527263228506817434796564168585494 61996564752026260167473915877048000544
3 526178816874 682653788347 476063425291
4 45887708296904 45887708297904 45887708323904 45887708311904
5 6627433380947979411089962012698836777513 6627433381711738702357850080066957781666 6627433387821813032500954619011925814890 6627433438993685547449455132676033093141 6627433392404368780108283023220651839808
4 421860197135 532816948430 331453194389 521759298690
11 333767259202070 333767259202073 333767259202196 333767259202103 333767259202151 333767259202172 333767259202145 333767259202190 333767259202079 333767259202142 333767259202133
5 6959440608500573797348743078668711599810 6959440609430068483884086056596640902483 6959440671706212481752065577767904181574 6959440659622781556792606864704823246825 6959440672635707168287408555695833484247
10 830763374237 937263882579 786020116823 451387759124 384749146501 910964348558 751990224767 838620069695 965185984705 600139972195
12 858640607830806 858640607830808 858640607830894 858640607830844 858640607830894 858640607830866 858640607830834 858640607830886 858640607830816 858640607830816 858640607830888 858640607830824
6 7640365390547244230782880092087399314454 7640365391278527747734715176416011407199 7640365406635481603723251947316865354844 7640365425648853044470964139860779766214 7640365438811956349603995657775797435624 7640365435886822281796655320461349064644
4 934113128354 967709209993 212718229625 420589890651
12 934548090873028 934548090873040 934548090873100 934548090873040 934548090873472 934548090873520 934548090873556 934548090873232 934548090873364 934548090873520 934548090873268 934548090873352
6 2682144858136032018891079346715365956883 2682144858625265438477124547460497121096 2682144883576169837365429785462186495959 2682144888468504033225881792913498138089 2682144859603732277649214948950759449522 2682144870856100928128254566088776226421
3 923889036196 758350481733 342198826758

예상 출력

Case #1: 0
Case #2: 3
Case #3: 28142269667917990242898884849
Case #4: 0
Case #5: 1
Case #6: 158543190373454948342916304656
Case #7: 0
Case #8: 7
Case #9: 356569437716108511304344104102
Case #10: 0
Case #11: 0
Case #12: 131772994680449773418589745807
Case #13: 73124109418
Case #14: 1
Case #15: 75196705947739120970586682831
Case #16: 0
Case #17: 9
Case #18: 69160518798000198384045843181
Case #19: 0
Case #20: 5
Case #21: 404326282910472031591197658867
Case #22: 0
Case #23: 7
Case #24: 178787292664929797028603781043
Case #25: 0
Case #26: 322
Case #27: 599803512263554298780308361082
Case #28: 0
Case #29: 1
Case #30: 114067715047397085818418777847
Case #31: 0
Case #32: 312576
Case #33: 38286825243234527639751888554
Case #34: 0
Case #35: 178
Case #36: 287369729974254056587424044204
Case #37: 716372590658
Case #38: 773
Case #39: 6655322540175451993504220622
Case #40: 0
Case #41: 267
Case #42: 70885758689617440623443034252
Case #43: 0
Case #44: 289
Case #45: 58318652366892362346728094559
Case #46: 0
Case #47: 0
Case #48: 272439479585894762412138033452
Case #49: 0
Case #50: 8
Case #51: 136685783852336009847609879680
Case #52: 0
Case #53: 457
Case #54: 244214184510758243325324717615
Case #55: 0
Case #56: 1
Case #57: 76196586314820401062231002173
Case #58: 0
Case #59: 0
Case #60: 468991536909796253131553401866
Case #61: 0
Case #62: 2
Case #63: 236876216123291728597816632698
Case #64: 0
Case #65: 1
Case #66: 256882483545562509046274095816
Case #67: 0
Case #68: 1
Case #69: 449661409577872938335769218801
Case #70: 0
Case #71: 0
Case #72: 173171411159675621506054963389
Case #73: 0
Case #74: 914
Case #75: 508420095810164706209577758586
Case #76: 0
Case #77: 2
Case #78: 414460437274869355494528310994
Case #79: 0
Case #80: 1
Case #81: 239867045482553592117614260200
Case #82: 0
Case #83: 1
Case #84: 28636833820116433506019080008
Case #85: 0
Case #86: 1
Case #87: 432914547693433663553580505256
Case #88: 0
Case #89: 96
Case #90: 50177505510533433253534928143
Case #91: 0
Case #92: 1
Case #93: 874676750256652850097481374963
Case #94: 0
Case #95: 0
Case #96: 47887614148925897354370624561
Case #97: 0
Case #98: 8
Case #99: 306887974522327630510884884575
Case #100: 0