{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\u003cem\u003e- Hmm... I asked for 400 drops, but there are 402 here.\u003c/em\u003e\u003c/p\u003e\n\n\u003cp\u003e\u003cem\u003e- 400 drops, we never make mistakes.\u003c/em\u003e\u003c/p\u003e\n\n\u003cp\u003eRussian cartoon _The Mystery of the Third Planet\u003c/p\u003e\n\n\u003cp\u003eDo you think that managing a restaurant is easy? That is not the case when all clients are pretty demanding.\u003c/p\u003e\n\n\u003cp\u003eYou are managing a restaurant, and every day a lot of people come and ask you to give them some drinks. As your restaurant has just recently opened, you don\u0027t have any vessels except two, which can accommodate \u003cstrong\u003ea\u003c/strong\u003e drops of liquid and \u003cstrong\u003eb\u003c/strong\u003e drops of liquid, respectively. In order not to make your clients wait (or at least to minimize their waiting time), you always have to determine the minimal number of steps required to obtain exactly \u003cstrong\u003ec\u003c/strong\u003e drops of liquid in one of the vessels.\u003c/p\u003e\n\n\u003cp\u003eAt the beginning both vessels are empty. The following operations are counted as steps:\u003c/p\u003e\n\n\u003cul\u003e\n\u003cp\u003e\u003cli\u003e emptying a vessel;\u003c/p\u003e\n\n\u003cp\u003e\u003cli\u003e filling a vessel;\u003c/p\u003e\n\n\u003cp\u003e\u003cli\u003e pouring liquid from one vessel to the other (without spilling) until one of the vessels is either full or empty.\u003c/p\u003e\n\n\u003c/ul\u003e\n\n\u003cp\u003eEventually you became tired to do it all by hand and decided to write a program which will help you calculate the minimum number of steps required in all these cases.\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eInput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eThe first line contains the number of test cases \u003cstrong\u003eT\u003c/strong\u003e (\u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003eT\u003c/strong\u003e ≤ \u003cstrong\u003e10^5\u003c/strong\u003e). Each of the next \u003cstrong\u003eT\u003c/strong\u003e lines contains one testcase and consists of three integers \u003cstrong\u003ea\u003c/strong\u003e, \u003cstrong\u003eb\u003c/strong\u003e and \u003cstrong\u003ec\u003c/strong\u003e (\u003cstrong\u003e1\u003c/strong\u003e ≤ \u003cstrong\u003ea\u003c/strong\u003e, \u003cstrong\u003eb\u003c/strong\u003e, \u003cstrong\u003ec\u003c/strong\u003e ≤ \u003cstrong\u003e10^9\u003c/strong\u003e).\u003c/p\u003e\n\n\u003cp\u003e\u003ch2\u003eOutput\u003c/h2\u003e\u003c/p\u003e\n\n\u003cp\u003eFor each test case print the minimum number of steps required to obtain exactly \u003cstrong\u003ec\u003c/strong\u003e drops of liquid in one of the vessels or \u003cstrong\u003e-1\u003c/strong\u003e if this is impossible.\u003c/p\u003e\n\n"}},{"title":"Example","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n2 5 4\n5 3 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n-1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}