Problem Description

Little Z is an active and lively child. One day, she stood at position \( b \) on the number line and prepared to start moving along the positive half-axis of the number line. Each time Little Z takes a step, she immediately advances \( a \) units along the positive half-axis of the number line. Interestingly, \( a \) and \( b \) are both positive integers, so the position Little Z is at any moment is also a positive integer.

Little Z's lucky number is a positive integer \( c \). She believes that if the position she moves to is exactly coprime with \( c \), then she considers this position a lucky position. Please help Little Z determine whether she can move to a lucky position; if she can, calculate any one number of steps \( n \) that allows her to reach a lucky position.

Concise problem statement: Given three positive integers \( a \), \( b \), and \( c \), determine if there exists a non-negative integer \( n \) such that \( (an+b, c)=1 \), where \( (\cdot, \cdot) \) denotes the greatest common divisor. If such an \( n \) exists, find any one solution.

Input Format

The first line contains a positive integer \( T \), representing the number of data groups. Each group of data is input consecutively.

For each group of data, the input is a line containing three positive integers \( a \), \( b \), and \( c \), as described in the problem statement.

For all input data, \( 1 \leq T \leq 10 \), \( 1 \leq a, b, c < 10^{2000} \), and all input data are given in decimal.

Output Format

For each group of data, output a line containing one integer. If no valid number of steps \( n \) can be found, output -1. Otherwise, output a non-negative integer representing a valid number of steps \( n \).

All output should be in decimal, with each line output not exceeding 2000 characters. The test data will ensure that there is a solution within the output length limit. Additionally, do not output extra spaces or any extraneous characters, and ensure there is a newline character at the end of the text, otherwise, it may affect the judgment of the evaluation program.

Sample Input and Output

Input Sample #1

3
1 2 3
1 3 6
2 2 2

Output Sample #1

0
2
-1

Input Sample #2

10
852473158087426181 40698107377421 34573878586
581501852629475409 3507820691986234 325392124094986
983001573592419694 12758046154806915 391181873366625
523432507089908187 22235351323484 99720444415644
547133061299817509 6492909838101120 234547940354112
315440975649541747 11555829815904864 467063676334080
439602165995515631 4284196383788100 23950691236800
8041598789940150 37468471223945472 3903034663348992
6871678354485379 19849006524667320 441009815372280
332133101579862271 12172161650895405 171736644454695

Output Sample #2

62
8653
209
9153
11
515
391
-1
109
23

Input Sample #3

```
10
12783455250264173814286920561815033129455292749111618918427759878900279810751984733300641240295647645498994599162724672629047892495532138517304022796851646558771922984858980119262334693601019798098147528413114685574056503715436537549292522354971173131279934494296523856354172666493759578559235721409803839003282397252589124075035701330994071273489705237262616797742375568061616753874936817653732331053918236491719070433469272496053789879577293093136499356430366004876174347137875860926532055047193332536966232985234902943131367685839673058435700772348235953215944653853083095646817090284623088732200913621558545052386885042144165328321547940688685206283677824239012495336775290807495043909817845678605221553727459510132354991460204987208647245314559868770002161766721560065585437486661777527998592610144754342130391951953419017996795637883263220168976979322596122704959150231743451325634540339716294155725269960803221336542937571792081037139459330357824733566717243006876271409335003836078762849002147189955692085715248990876391981766255248969629842537112053108152500087637823362918408326282337474710378962500600610349693653993027550952316316670853506306449406813119139788643083838328211821035371108143341935600097829865434811530599524028359788523071541453847264583333710123798328108566001918896610874808288975227629962146563973302514985616457681694941096019675649638734197123802474002128602378887819093164289307336054709619640526458697226534314914555408935927007541621264931926037372185067494993786587959784478212898791101939208908593012681830298437720655297000446578120709407231943461962332188295524845355039581215838303320770764898539181428691049707794809167418051510339852221874475513290850113263684417176656727864613919612116766407162187109690857320432723321345280123657010476175722098557540458136644293946857141877052604661078603646541069981640502793371518767316335666923800759018243396579180815135128964451989008345328070525364016754509674392674714149756548873402632728838590166371254746489441 44924584934298356258235247139515550277657144458132498920711701319209046837005601491725325650104446122603984225820428968942657142821237106326448598486364447934821424060473757046276786629098102167527673538036553991151541273947919892025604291204237290090107405121447367158704606912774391763259262891780036252203471524703366851604160103580747787054352898175420368862462141358161847230152789331018843086484212593329912348222277059280691902695892264715387133615653190723569903496603187488405999349317653662737078745787648567769844869079173449207207336861979579973618425342144127230835761987073422043679970470242803266680165591525343971536842802558791640600538155258124140299021534839210512287020369411255622076001574169024425018843663426370052763964519938206410908872864827508775245746148576446182132439091342389634159768379083582026347741997321884886737792957927430751871598993475295804545197485174215520946553554142369

见题面 Input 部分

见题面 Output 部分