You are at the side of a river. You are given a m litre jug and a n litre jug . Both the jugs are initially empty. The jugs dont have markings to allow measuring smaller quantities. You have to use the jugs to measure d litres of water . Determine the minimum no of operations to be performed to obtain d litres of water in one of the jugs.
The operations you can perform are:
	Empty a Jug
	Fill a Jug
	Pour water from one jug to the other until one of the jugs is either empty or full.
 
Example 1:
Input: m = 3, n = 5, d = 4
Output: 6
Explanation: Operations are as follow-
1. Fill up the 5 litre jug.
2. Then fill up the 3 litre jug using 5 litre
   jug. Now 5 litre jug contains 2 litre water.
3. Empty the 3 litre jug.
4. Now pour the 2 litre of water from 5 litre 
   jug to 3 litre jug.
5. Now 3 litre jug contains 2 litre of water 
   and 5 litre jug is empty. Now fill up the 
   5 litre jug.
6. Now fill one litre of water from 5 litre jug 
   to 3 litre jug. Now we have 4 litre water in 
   5 litre jug.
Example 2:
Input: m = 8, n = 56, d = 46
Output: -1
Explanation: Not possible to fill any one of 
the jug with 46 litre of water.
 
Your Task:
You don't need to read or print anything. Your task is to complete the function minSteps() which takes m, n and d ans input parameter and returns the minimum number of operation to fill d litre of water in any of the two jug.
 
Expected Time Comeplxity: O(d)
Expected Space Complexity: O(1)
Constraints:
1 ≤ n,m ≤ 100
1 ≤ d ≤ 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3



class Solution:

	def minSteps(self, m, n, d):

		# Code here

Solutions:
class Solution:

	def gcd(self, a, b):
		if b == 0:
			return a
		return self.gcd(b, a % b)

	def solve(self, to, frmJug, target):
		st = frmJug
		toJug = 0
		count = 1
		while st != target and toJug != target:
			temp = min(st, to - toJug)
			toJug += temp
			st -= temp
			count += 1
			if st == target or toJug == target:
				break
			if st == 0:
				st = frmJug
				count += 1
			if toJug == to:
				toJug = 0
				count += 1
		return count

	def minSteps(self, n, m, d):
		if m > n:
			(m, n) = (n, m)
		if d % self.gcd(m, n) != 0:
			return -1
		if m == d or n == d:
			return 1
		if d > n:
			return -1
		op1 = self.solve(m, n, d)
		op2 = self.solve(n, m, d)
		return min(op1, op2)


class Solution:

	def minSteps(self, m, n, d):

		def gcd(a, b):
			if b == 0:
				return a
			return gcd(b, a % b)
		if m > n:
			(m, n) = (n, m)
		if m == d or n == d:
			return 1
		if d > n:
			return -1
		if d % gcd(n, m) is not 0:
			return -1

		def Pour(toJugcap, fromJugcap, d):
			fromJug = fromJugcap
			toJug = 0
			step = 1
			while fromJug is not d and toJug is not d:
				temp = min(fromJug, toJugcap - toJug)
				toJug = toJug + temp
				fromJug = fromJug - temp
				step += 1
				if fromJug == d or toJug == d:
					break
				if fromJug == 0:
					fromJug += fromJugcap
					step += 1
				if toJug == toJugcap:
					toJug = 0
					step += 1
			return step
		return min(Pour(n, m, d), Pour(m, n, d))


import sys
sys.setrecursionlimit(1000000)

class Solution:

	def minSteps(self, m, n, d):

		def gcd(a, b):
			if b == 0:
				return a
			return gcd(b, a % b)
		if m > n:
			(m, n) = (n, m)
		if n == d or m == d:
			return 1
		if d > n:
			return -1
		if d % gcd(n, m) != 0:
			return -1

		def solve(m, n, d):
			a = m
			b = 0
			r = 1
			while a != d or b != d:
				x = a if a < n - b else n - b
				b += x
				a -= x
				r += 1
				if a == d or b == d:
					break
				if a == 0:
					a = m
					r += 1
				if b == n:
					b = 0
					r += 1
			return r
		r1 = solve(m, n, d)
		r2 = solve(n, m, d)
		return r1 if r1 < r2 else r2


from collections import deque

class Solution:

	def minSteps(self, m, n, d):

		def extended_gcd(a, b):
			if a == 0:
				return (b, 0, 1)
			(gcd, x1, y1) = extended_gcd(b % a, a)
			x = y1 - b // a * x1
			y = x1
			return (gcd, x, y)

		def gcd(a, b):
			if b == 0:
				return a
			return gcd(b, a % b)
		(g, a, b) = extended_gcd(m, n)
		if d > n:
			return -1
		if d % g:
			return -1

		def jugsum(v1, c1, v2, c2, counter):
			if c1 == d or c2 == d:
				return 1
			while v1 != d and v2 != d:
				if v1 == 0:
					v1 = c1
					counter += 1
				tmp = v2
				v2 = min(v2 + v1, c2)
				v1 -= v2 - tmp
				counter += 1
				if v1 == d or v2 == d:
					break
				if v2 == c2:
					v2 = 0
					counter += 1
			return counter
		return min(jugsum(0, m, 0, n, 0), jugsum(0, n, 0, m, 0))


from collections import deque

class Solution:

	def minSteps(self, m, n, d):

		def gcd(a, b):
			if b == 0:
				return a
			return gcd(b, a % b)

		def Pour(toJugCap, fromJugCap, d):
			fromJug = fromJugCap
			toJug = 0
			step = 1
			while fromJug != d and toJug != d:
				temp = min(fromJug, toJugCap - toJug)
				toJug = toJug + temp
				fromJug = fromJug - temp
				step = step + 1
				if fromJug == d or toJug == d:
					break
				if fromJug == 0:
					fromJug = fromJugCap
					step = step + 1
				if toJug == toJugCap:
					toJug = 0
					step = step + 1
			return step
		if d > n:
			return -1
		if d % gcd(n, m):
			return -1
		return min(Pour(n, m, d), Pour(m, n, d))


from collections import deque

class Solution:

	def minSteps(self, m, n, d):
		visited = set()
		q = deque()
		q.append(((0, 0), 0))
		visited.add((0, 0))
		while q:
			(curr_state, steps) = q.popleft()
			(curr_jug1_cntnt, curr_jug2_cntnt) = curr_state
			next_states = [(0, curr_jug2_cntnt), (curr_jug1_cntnt, 0), (m, curr_jug2_cntnt), (curr_jug1_cntnt, n), (curr_jug1_cntnt + min(curr_jug2_cntnt, m - curr_jug1_cntnt), curr_jug2_cntnt - min(curr_jug2_cntnt, m - curr_jug1_cntnt)), (curr_jug1_cntnt - min(curr_jug1_cntnt, n - curr_jug2_cntnt), curr_jug2_cntnt + min(curr_jug1_cntnt, n - curr_jug2_cntnt))]
			for next_state in next_states:
				if next_state not in visited:
					if next_state[0] == d or next_state[1] == d:
						return steps + 1
					visited.add(next_state)
					q.append((next_state, steps + 1))
		return -1


from collections import deque

class Solution:

	def minSteps(self, m, n, w):
		q = deque()
		q.append([0, 0])
		s = set()
		s.add((0, 0))
		op = 0
		while q:
			l = len(q)
			for i in range(l):
				(x, y) = q.popleft()
				if x == w or y == w:
					return op
				d = [[x, n], [m, y], [0, y], [x, 0]]
				for (i, j) in d:
					if (i, j) not in s:
						q.append([i, j])
						s.add((i, j))
				if x + y <= n:
					if (0, x + y) not in s:
						q.append([0, x + y])
						s.add((0, x + y))
				else:
					r = x - (n - y)
					if (r, n) not in s:
						q.append([r, n])
						s.add((r, n))
				if x + y <= m:
					if (x + y, 0) not in s:
						q.append([x + y, 0])
						s.add((x + y, 0))
				else:
					r = y - (m - x)
					if (m, r) not in s:
						q.append([m, r])
						s.add((m, r))
			op += 1
		return -1


import math

class Solution:

	def util(self, tjf, fjf, d):
		tj = 0
		fj = fjf
		steps = 1
		while tj is not d and fj is not d:
			temp = min(fj, tjf - tj)
			fj -= temp
			tj += temp
			steps += 1
			if tj == d or fj == d:
				break
			if fj == 0:
				fj = fjf
				steps += 1
			if tj == tjf:
				tj = 0
				steps += 1
		return steps

	def minSteps(self, m, n, d):
		m = min(m, n)
		n = max(m, n)
		if d > n:
			return -1
		gcdMN = math.gcd(n, m)
		if d % gcdMN != 0:
			return -1
		return min(self.util(m, n, d), self.util(n, m, d))


class Solution:

	def minSteps(self, m, n, d):
		if d == m or d == n:
			return 1
		if m == n:
			return -1
		k = m
		c = 2
		c1 = 0
		c2 = 0
		while k:
			if d == k:
				c1 = c
				break
			if k < m:
				c += 4
			else:
				c += 2
			k += m
			if k >= n:
				k -= n
		if not c1:
			return -1
		k = n - m
		c = 2
		while k:
			if d == k:
				c2 = c
			c += 2
			k -= m
			if k < 0:
				c += 2
				k += n
		return min(c1, c2)


from collections import deque

class Solution:

	def minSteps(self, m, n, d):
		seen = set()
		state = (0, 0)
		Q = deque([(state, 0)])
		while Q:
			(s, steps) = Q.popleft()
			seen.add(s)
			if s[0] == d or s[1] == d:
				return steps
			X = s[0]
			Y = s[1]
			if (m, Y) not in seen:
				Q.append(((m, Y), steps + 1))
			if (X, n) not in seen:
				Q.append(((X, n), steps + 1))
			if (0, Y) not in seen:
				Q.append(((0, Y), steps + 1))
			if (X, 0) not in seen:
				Q.append(((X, 0), steps + 1))
			val = (X - (n - Y), n) if X - (n - Y) >= 0 else (0, X + Y)
			if val not in seen:
				Q.append((val, steps + 1))
			val = (m, Y - (m - X)) if Y - (m - X) >= 0 else (X + Y, 0)
			if val not in seen:
				Q.append((val, steps + 1))
		return -1


class Solution:

	def minSteps(self, m, n, d):

		def gcd(a, b):
			if b == 0:
				return a
			return gcd(b, a % b)

		def pour(fromjugCap, tojugCap, d):
			c = 1
			(fromjug, tojug) = (fromjugCap, 0)
			while d != fromjug or d != tojug:
				pourable = min(fromjug, tojugCap - tojug)
				fromjug -= pourable
				tojug += pourable
				c += 1
				if d == fromjug or d == tojug:
					break
				if fromjug == 0:
					fromjug = fromjugCap
					c += 1
				if tojug == tojugCap:
					tojug = 0
					c += 1
			return c
		if d > max(m, n) or d % gcd(m, n) != 0:
			return -1
		if d == m or d == n:
			return 1
		return min(pour(m, n, d), pour(n, m, d))
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(m, n, d) = map(int, input().strip().split())
		ob = Solution()
		ans = ob.minSteps(m, n, d)
		print(ans)


class Solution:

	def minSteps(self, m, n, d):
		if d == m or d == n:
			return 1
		if m == n:
			return -1
		k = m
		c = 2
		c1 = 0
		c2 = 0
		while k:
			if d == k:
				c1 = c
				break
			if k < m:
				c = c + 4
			else:
				c = c + 2
			k = k + m
			if k >= n:
				k = k - n
		if not c1:
			return -1
		k = n - m
		c = 2
		while k:
			if d == k:
				c2 = c
			c = c + 2
			k = k - m
			if k < 0:
				c = c + 2
				k = k + n
		return min(c1, c2)
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(m, n, d) = map(int, input().strip().split())
		ob = Solution()
		ans = ob.minSteps(m, n, d)
		print(ans)


class Solution:

	def gcd(self, a, b):
		if b == 0:
			return a
		return self.gcd(b, a % b)

	def Pour(self, toJugCap, fromJugCap, d):
		fromJug = fromJugCap
		toJug = 0
		step = 1
		while fromJug != d and toJug != d:
			temp = min(fromJug, toJugCap - toJug)
			toJug += temp
			fromJug -= temp
			step = step + 1
			if fromJug == d or toJug == d:
				break
			if fromJug == 0:
				fromJug = fromJugCap
				step += 1
			if toJug == toJugCap:
				toJug = 0
				step += 1
		return step

	def minSteps(self, m, n, d):
		if m > n:
			(m, n) = (n, m)
		if d > n:
			return -1
		if d % self.gcd(n, m) != 0:
			return -1
		return min(self.Pour(n, m, d), self.Pour(m, n, d))
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(m, n, d) = map(int, input().strip().split())
		ob = Solution()
		ans = ob.minSteps(m, n, d)
		print(ans)


from collections import deque

class Solution:

	def minSteps(self, m, n, d):

		def gcd(a, b):
			if b == 0:
				return a
			return gcd(b, a % b)

		def pour(fr, to, d):
			f = fr
			t = 0
			step = 1
			while t != d and f != d:
				temp = min(f, to - t)
				t += temp
				f -= temp
				step += 1
				if f == d or t == d:
					return step
				if f == 0:
					f = fr
					step += 1
				if t == to:
					t = 0
					step += 1
			return step
		if d > n:
			return -1
		if d % gcd(m, n) != 0:
			return -1
		return min(pour(n, m, d), pour(m, n, d))
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		(m, n, d) = map(int, input().strip().split())
		ob = Solution()
		ans = ob.minSteps(m, n, d)
		print(ans)


class Solution:

	def gcd(self, a, b):
		if b == 0:
			return a
		return self.gcd(b, a % b)

	def solve(self, to_cap, from_cap, d):
		from_jug = from_cap
		to_jug = 0
		step = 1
		while from_jug != d and to_jug != d:
			temp = min(from_jug, to_cap - to_jug)
			to_jug = to_jug + temp
			from_jug = from_jug - temp
			step = step + 1
			if from_jug == d or to_jug == d:
				break
			if from_jug == 0:
				from_jug = from_cap
				step = step + 1
			if to_jug == to_cap:
				to_jug = 0
				step = step + 1
		return step

	def minSteps(self, m, n, d):
		if m == d or n == d:
			return 1
		if m == n:
			return -1
		if m >= n:
			(n, m) = (m, n)
		if d > n:
			return -1
		if d % self.gcd(n, m) != 0:
			return -1
		return min(self.solve(m, n, d), self.solve(n, m, d))


class Solution:

	def minSteps(self, m, n, d):
		current = 0
		total_steps = 0
		encounters = -1
		if m == d or n == d:
			return 1
		while True:
			if current == n:
				total_steps += 1
				break
			if current + m > n:
				total_steps += 2
				current = (current + m) % n
				if current == d:
					encounters = [total_steps, total_steps + 3]
				total_steps += 2
			else:
				current += m
				total_steps += 2
				if current == d:
					encounters = [total_steps, total_steps + 1]
		return -1 if encounters == -1 else min(encounters[0], total_steps - encounters[1])


class Solution:

	def __init__(self):
		self.c = 0

	def gcd(self, a, b):
		if a == 0:
			return b
		else:
			return self.gcd(b % a, a)

	def solve(self, a, b, d, n, m):
		if a == d or b == d:
			return
		else:
			if b == 0:
				self.c += 1
				self.solve(a, m, d, n, m)
				return
			if a == n:
				self.c += 1
				self.solve(0, b, d, n, m)
				return
			else:
				self.c += 1
				if b < n - a:
					self.solve(a + b, 0, d, n, m)
					return
				else:
					self.solve(n, b - (n - a), d, n, m)
					return

	def minSteps(self, m, n, d):
		if d > n and d > m:
			return -1
		if d % self.gcd(m, n) != 0:
			return -1
		op1 = op2 = 0
		self.solve(0, 0, d, m, n)
		op1 = self.c
		self.c = 0
		self.solve(0, 0, d, n, m)
		op2 = self.c
		return min(op1, op2)


class Solution:

	def minSteps(self, m, n, d):

		def gcd(a, b):
			if a % b == 0:
				return b
			return gcd(b, a % b)
		if d % gcd(n, m) != 0:
			return -1
		if d > n:
			return -1

		def pour(fromCup, toCup, d):
			fromC = fromCup
			toC = 0
			step = 1
			while fromC != d and toC != d:
				temp = min(fromC, toCup - toC)
				fromC -= temp
				toC += temp
				step += 1
				if fromC == d or toC == d:
					break
				if fromC == 0:
					fromC = fromCup
					step += 1
				if toC == toCup:
					toC = 0
					step += 1
			return step
		return min(pour(m, n, d), pour(n, m, d))


from collections import deque

class Solution:

	def minSteps(self, m, n, d):
		if m > n:
			return self.minSteps(n, m, d)
		vis = [[False] * (n + 1) for _ in range(n + 1)]
		q = deque([(0, 0)])
		vis[0][0] = True
		cnt = 0
		while q:
			for _ in range(len(q)):
				(j1, j2) = q.popleft()
				if j1 == d or j2 == d:
					return cnt
				nj1 = 0
				nj2 = j2
				if vis[nj1][nj2] == False:
					vis[nj1][nj2] = True
					q.append((nj1, nj2))
				nj1 = j1
				nj2 = 0
				if vis[nj1][nj2] == False:
					vis[nj1][nj2] = True
					q.append((nj1, nj2))
				nj1 = n
				nj2 = j2
				if vis[nj1][nj2] == False:
					vis[nj1][nj2] = True
					q.append((nj1, nj2))
				nj1 = j1
				nj2 = m
				if vis[nj1][nj2] == False:
					vis[nj1][nj2] = True
					q.append((nj1, nj2))
				nj1 = max(0, j1 - (m - j2))
				nj2 = min(m, j2 + j1)
				if vis[nj1][nj2] == False:
					vis[nj1][nj2] = True
					q.append((nj1, nj2))
				nj1 = min(n, j1 + j2)
				nj2 = max(0, j2 - (n - j1))
				if vis[nj1][nj2] == False:
					vis[nj1][nj2] = True
					q.append((nj1, nj2))
			cnt += 1
		return -1


from collections import deque
from collections import defaultdict

class Solution:

	def minSteps(self, m, n, d):
		x = 0
		y = 0
		q = deque()
		q.append((x, y))
		q.append((None, None))
		pair = defaultdict(int)
		step = 0
		pair[x, y] = 1
		while len(q) > 0:
			(x, y) = q.popleft()
			if x == d or y == d:
				return step
			if x == None and y == None:
				if len(q) == 0:
					break
				q.append((None, None))
				step += 1
				continue
			if x > m or y > n:
				return -1
			if x:
				if pair[x - x, y] == 0:
					pair[x - x, y] = 1
					q.append((x - x, y))
			if y:
				if pair[x, y - y] == 0:
					pair[x, y - y] = 1
					q.append((x, y - y))
			if x + m <= m:
				if pair[x + m, y] == 0:
					pair[x + m, y] = 1
					q.append((x + m, y))
			if y + n <= n:
				if pair[x, y + n] == 0:
					pair[x, y + n] = 1
					q.append((x, y + n))
			cap_x = m - x
			if cap_x >= y:
				if pair[x + y, y - y] == 0:
					pair[x + y, y - y] = 1
					q.append((x + y, y - y))
			else:
				new_c = y - cap_x
				if pair[x + cap_x, y - cap_x] == 0:
					pair[x + cap_x, y - cap_x] = 1
					q.append((x + cap_x, y - cap_x))
			cap_y = n - y
			if cap_y >= x:
				if pair[x - x, y + x] == 0:
					pair[x - x, y + x] = 1
					q.append((x - x, y + x))
			else:
				new_c = cap_y
				if pair[x - new_c, y + new_c] == 0:
					pair[x - new_c, y + new_c] = 1
					q.append((x - new_c, y + new_c))
		return -1


class Solution:

	def minSteps(self, m, n, d):

		def gcd(a, b):
			if b == 0:
				return a
			(a, b) = (b, a % b)
			return gcd(a, b)
		if d > max(m, n) or d % gcd(m, n) != 0:
			return -1

		def minMoves(x, y, C1, C2, d):
			if x == d or y == d:
				return 0
			if y == C2:
				y = 0
			elif x == 0:
				x = C1
			elif x > C2 - y:
				x = x - C2 + y
				y = C2
			else:
				y += x
				x = 0
			return 1 + minMoves(x, y, C1, C2, d)
		return min(minMoves(0, 0, m, n, d), minMoves(0, 0, n, m, d))


class Solution:

	def minSteps(self, m, n, d):
		if m == d or n == d:
			return 1
		ns = n
		ms = 0
		steps = 1
		memo = {}
		while True:
			if ns > m:
				ns = ns - (m - ms)
				ms = ms + (m - ms)
				steps += 1
				if ms == d or ns == d:
					break
				ms = 0
				ns = ns
				steps += 1
				if ms == d or ns == d:
					break
			else:
				ms = ns
				ns = 0
				steps += 1
				if ms == d or ns == d:
					break
				ns = n
				ms = ms
				steps += 1
				if ms == d or ns == d:
					break
			if memo.get((ns, ms)) != None:
				break
			else:
				memo[ns, ms] = 1
		if ms != d and ns != d:
			steps = -1
		steps2 = 1
		ms = m
		ns = 0
		memo2 = {}
		while True:
			if ns + m <= n:
				ns = ns + ms
				ms = 0
				steps2 += 1
				if ms == d or ns == d:
					break
				ms = m
				steps2 += 1
				if ms == d or ns == d:
					break
			else:
				ms = ms - (n - ns)
				ns = ns + (n - ns)
				steps2 += 1
				if ms == d or ns == d:
					break
				ns = 0
				ms = ms
				steps2 += 1
				if ms == d or ns == d:
					break
			if memo2.get((ns, ms)) != None:
				break
			else:
				memo2[ns, ms] = 1
		if ms != d and ns != d:
			steps2 = -1
		if steps == -1 and steps2 == -1:
			return -1
		elif steps == -1:
			return steps2
		elif steps2 == -1:
			return steps
		else:
			return min(steps2, steps)


from math import gcd

class Solution:

	def minSteps(self, m, n, d):
		return mins(m, n, d)

def find(m, n, d):
	(x, y, c1) = (m, 0, 1)
	while not (x == d or y == d):
		val = min(x, n - y)
		(x, y) = (x - val, y + val)
		c1 += 1
		if x == d or y == d:
			break
		if x == 0:
			x = m
			c1 += 1
		if y == n:
			y = 0
			c1 += 1
	return c1

def mins(m, n, d):
	if m < d and d > n:
		return -1
	if d % gcd(m, n) != 0:
		return -1
	(c1, c2) = (0, 0)
	(x, y) = (m, 0)
	a = find(m, n, d)
	b = find(n, m, d)
	return min(a, b)


class Solution:

	def gcd(self, a, b):
		if b == 0:
			return a
		return self.gcd(b, a % b)

	def min_step(self, fill, empty, d):
		steps = 0
		from_jug = fill
		to_jug = 0
		steps += 1
		while from_jug != d and to_jug != d:
			rem = min(from_jug, empty - to_jug)
			to_jug += rem
			from_jug -= rem
			steps += 1
			if to_jug == d or from_jug == d:
				break
			if from_jug == 0:
				from_jug = fill
				steps += 1
			if to_jug == empty:
				to_jug = 0
				steps += 1
		return steps

	def minSteps(self, m, n, d):
		if m > n:
			return -1
		if n < d:
			return -1
		div = self.gcd(m, n)
		if d % div != 0:
			return -1
		step1 = self.min_step(m, n, d)
		step2 = self.min_step(n, m, d)
		return min(step1, step2)
		return 0


import math

class Solution:

	def minSteps(self, m, n, d):

		def pour(from_jug, to_jug, d):
			j1 = from_jug
			j2 = 0
			steps = 1
			while j1 != d and j2 != d:
				temp = min(j1, to_jug - j2)
				j1 -= temp
				j2 += temp
				steps += 1
				if j1 == d or j2 == d:
					break
				if j1 == 0:
					j1 = from_jug
					steps += 1
				if j2 == to_jug:
					j2 = 0
					steps += 1
			return steps
		if d % math.gcd(m, n):
			return -1
		if d > n:
			return -1
		return min(pour(n, m, d), pour(m, n, d))


def solve(to_cap, from_cap, d):
	from_ = from_cap
	to = 0
	step = 1
	while from_ != d and to != d:
		temp = min(from_, to_cap - to)
		to += temp
		from_ -= temp
		step += 1
		if to == d or from_ == d:
			break
		if from_ == 0:
			from_ = from_cap
			step += 1
		if to == to_cap:
			to = 0
			step += 1
	return step
import math

class Solution:

	def minSteps(self, m, n, d):
		g = math.gcd(m, n)
		if d % g > 0 or d > n:
			return -1
		else:
			ans = min(solve(m, n, d), solve(n, m, d))
			return ans


from collections import deque

class Solution:

	def minSteps(self, m, n, d):
		queue = deque()
		queue.append([0, 0, 0])
		visited = [set() for i in range(m + 1)]
		visited[0].add(0)
		while queue:
			(p, q, count) = queue.popleft()
			(x, y) = (p, q)
			if p == d or q == d:
				return count
			if n not in visited[x]:
				y = n
				visited[x].add(y)
				queue.append([x, y, count + 1])
				(x, y) = (p, q)
			if y not in visited[m]:
				x = m
				visited[x].add(y)
				queue.append([x, y, count + 1])
				(x, y) = (p, q)
			if 0 not in visited[x]:
				y = 0
				visited[x].add(y)
				queue.append([x, y, count + 1])
				(x, y) = (p, q)
			if y not in visited[0]:
				x = 0
				visited[x].add(y)
				queue.append([x, y, count + 1])
				(x, y) = (p, q)
			if 0 not in visited[m]:
				x = m
				y = 0
				visited[x].add(y)
				queue.append([x, y, count + 1])
				(x, y) = (p, q)
			if n not in visited[0]:
				x = 0
				y = n
				visited[x].add(y)
				queue.append([x, y, count + 1])
				(x, y) = (p, q)
			if y - min(m - x, y) not in visited[x + min(m - x, y)]:
				(x, y) = (x + min(m - x, y), y - min(m - x, y))
				visited[x].add(y)
				queue.append([x, y, count + 1])
				(x, y) = (p, q)
			if y + min(n - y, x) not in visited[x - min(n - y, x)]:
				(x, y) = (x - min(n - y, x), y + min(n - y, x))
				visited[x].add(y)
				queue.append([x, y, count + 1])
		return -1


from collections import deque

class Solution:

	def minSteps(self, m, n, d):
		visited = set()
		result = 1000000
		q = deque()
		q.append((0, 0, 0))
		visited.add((0, 0))
		while q:
			(x, y, val) = q.popleft()
			if x == d or y == d:
				return val
			val += 1
			if (x, 0) not in visited:
				visited.add((x, 0))
				q.append((x, 0, val))
			if (0, y) not in visited:
				visited.add((0, y))
				q.append((0, y, val))
			if (x, n) not in visited:
				visited.add((x, n))
				q.append((x, n, val))
			if (m, y) not in visited:
				visited.add((m, y))
				q.append((m, y, val))
			temp = x + y if x + y <= m else m
			if (temp, x + y - temp) not in visited:
				visited.add((temp, 0))
				q.append((temp, x + y - temp, val))
			temp = x + y if x + y <= n else n
			if (x + y - temp, temp) not in visited:
				visited.add((x + y - temp, temp))
				q.append((x + y - temp, temp, val))
		return -1


class Solution:

	def gcd(self, a, b):
		if b == 0:
			return a
		return self.gcd(b, a % b)

	def find_min_steps(self, fill, empty, d):
		steps = 0
		from_jug = fill
		to_jug = 0
		steps = steps + 1
		while from_jug != d and to_jug != d:
			rem = min(from_jug, empty - to_jug)
			to_jug += rem
			from_jug -= rem
			steps = steps + 1
			if from_jug == d or to_jug == d:
				break
			if from_jug == 0:
				from_jug = fill
				steps = steps + 1
			if to_jug == empty:
				to_jug = 0
				steps = steps + 1
		return steps

	def minSteps(self, m, n, d):
		gc = self.gcd(m, n)
		if m > n:
			return -1
		if d % gc != 0:
			return -1
		if n < d:
			return -1
		min_step1 = self.find_min_steps(n, m, d)
		min_step2 = self.find_min_steps(m, n, d)
		steps = min(min_step1, min_step2)
		return steps


class Solution:

	def gcd(self, a, b):
		if b == 0:
			return a
		return self.gcd(b, a % b)

	def go(self, fromCap, toCap, d):
		step = 1
		fromBucket = fromCap
		toBucket = 0
		while fromBucket != d and toBucket != d:
			temp = min(fromBucket, toCap - toBucket)
			fromBucket -= temp
			toBucket += temp
			step += 1
			if fromBucket == d or toBucket == d:
				break
			if fromBucket == 0:
				fromBucket = fromCap
				step += 1
			if toBucket == toCap:
				toBucket = 0
				step += 1
		return step

	def minSteps(self, m, n, d):
		c = self.gcd(m, n)
		if d % c:
			return -1
		if d > n:
			return -1
		return min(self.go(m, n, d), self.go(n, m, d))