Given two integers A and B.Find out the number of steps required to repeatedly subtract the smaller of the two from the larger until one of them becomes 0.
Example 1:
Input:
A=5,B=13
Output:
6
Explanation:
The steps are as follows:
(5,13)->(5,8)->(5,3)->(2,3)->(2,1)->(1,1)->(1,0)
Thus, 6 steps are required.
Example 2:
Input:
A=5,B=15
Output:
3
Explanation:
The steps are as follows:
(5,15)->(5,10)->(5,5)->(5,0).
Thus, 3 steps are required.
Your Task:
You don't need to read input or print anything. Your task is to complete the function repeatedSubtraction() which takes two integers A and B as input parameters and returns the number of steps required to repeatedly subtract until one of the numbers becomes 0.
Expected Time Complexity:O(Log(max(A,B))
Expected Auxillary Space:O(1)
Constraints:
1<=A,B<=10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Mathematics

Starter code: #User function Template for python3



class Solution:

    def repeatedSubtraction(self, A, B):

        #code here

Solutions:
class Solution:

	def repeatedSubtraction(self, A, B):
		a = 0
		while A != 0 and B != 0:
			if A > B:
				A = A - B
				a = a + 1
			else:
				B = B - A
				a = a + 1
		return a


class Solution:

	def repeatedSubtraction(self, a, b):
		c = 0
		while a and b:
			t = abs(b - a)
			if a > b:
				a = t
			else:
				b = t
			c += 1
		return c


class Solution:

	def repeatedSubtraction(self, A, B):
		if A > B:
			if A % B == 0:
				return A // B
			else:
				return math.floor(A // B + self.repeatedSubtraction(B, A % B))
		elif B % A == 0:
			return B // A
		else:
			return math.floor(B // A + self.repeatedSubtraction(A, B % A))


class Solution:

	def repeatedSubtraction(self, A, B):
		count = 0
		count = 0
		if A < B:
			A = A ^ B
			B = A ^ B
			A = A ^ B
		count += int(A / B)
		while A % B:
			C = B
			B = A % B
			A = C
			count += int(A / B)
		return count


def countSteps(x, y):
	if x % y == 0:
		return math.floor(x / y)
	return math.floor(x / y + countSteps(y, x % y))

class Solution:

	def repeatedSubtraction(self, A, B):
		return countSteps(A, B)


class Solution:

	def repeatedSubtraction(self, A, B):
		count = 0
		while 1:
			if A == 0 or B == 0:
				break
			if A == B:
				count += 1
				break
			if A > B:
				count += A // B
				A = A % B
				(A, B) = (B, A)
			else:
				(B, A) = (A, B)
		return count


class Solution:

	def repeatedSubtraction(self, A, B):
		y = min(A, B)
		x = max(A, B)
		if x % y == 0:
			return x // y
		return x // y + ob.repeatedSubtraction(y, x % y)


class Solution:

	def modifiedGcd(self, A, B):
		if A % B == 0:
			return A // B
		return A // B + self.modifiedGcd(B, A % B)

	def repeatedSubtraction(self, A, B):
		return self.modifiedGcd(A, B)
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(A, B) = map(int, input().strip().split(' '))
		ob = Solution()
		print(ob.repeatedSubtraction(A, B))


class Solution:

	def repeatedSubtraction(self, a, b):
		x = max(a, b)
		y = min(a, b)
		if x % y == 0:
			return x // y
		return x // y + self.repeatedSubtraction(y, x % y)
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(A, B) = map(int, input().strip().split(' '))
		ob = Solution()
		print(ob.repeatedSubtraction(A, B))


def calc(c, a, b):
	d = min(a, b)
	e = max(a, b)
	if d == 0:
		return c
	c += e // d
	return calc(c, d, e % d)

class Solution:

	def repeatedSubtraction(self, A, B):
		c = 0
		return calc(c, A, B)
import math
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(A, B) = map(int, input().strip().split(' '))
		ob = Solution()
		print(ob.repeatedSubtraction(A, B))


class Solution:

	def repeatedSubtraction(self, A, B):
		if A > B:
			(A, B) = (B, A)
		ans = 0
		while A != 0:
			ans = ans + B // A
			B = B % A
			(A, B) = (B, A)
		return ans


class Solution:

	def repeatedSubtraction(self, A, B):
		count = 0
		while min(A, B) > 0:
			if A < B:
				(A, B) = (B, A)
			count += A // B
			A %= B
		return count


class Solution:

	def repeatedSubtraction(self, A, B):
		if A == 0 or B == 0:
			return 0
		if A > B:
			return A // B + self.repeatedSubtraction(A % B, B)
		else:
			return B // A + self.repeatedSubtraction(A, B % A)


class Solution:

	def repeatedSubtraction(self, A, B):
		COUNT = 0
		while A != 0 or B != 0:
			if A < B:
				smol = A
				bigg = B
			else:
				smol = B
				bigg = A
			COUNT += int(bigg / smol)
			if bigg % smol == 0:
				return COUNT
			else:
				bigg = bigg % smol
			A = smol
			B = bigg


class Solution:

	def repeatedSubtraction(self, A, B):
		if A == 1 or B == 1:
			return max(A, B)
		C = 0
		while A > 0 and B > 0:
			if A >= B:
				A -= B
			elif B > A:
				B -= A
			C += 1
		return C


import math

class Solution:

	def repeatedSubtraction(self, a, b):
		if a % b == 0:
			return a // b
		return a // b + self.repeatedSubtraction(b, a % b)


class Solution:

	def repeatedSubtraction(self, A, B):
		c = 0
		while A > 0 and B > 0:
			if A > B:
				c += A // B
				A = A % B
			else:
				c += B // A
				B = B % A
		return c


import math

class Solution:

	def repeatedSubtraction(self, A, B):
		if A % B == 0:
			return math.floor(A / B)
		return math.floor(A / B + self.repeatedSubtraction(B, A % B))


class Solution:

	def repeatedSubtraction(self, A, B):
		count = 0
		while A != 0 and B != 0:
			if A > B:
				q = A // B
				A = A - q * B
				count += q
			else:
				q = B // A
				B = B - q * A
				count += q
		return count


class Solution:

	def repeatedSubtraction(self, A, B):
		if A <= 0 or B <= 0:
			return 0
		elif A > B:
			return A // B + self.repeatedSubtraction(A % B, B)
		elif A <= B:
			return B // A + self.repeatedSubtraction(A, B % A)


import math

class Solution:

	def repeatedSubtraction(self, x, y):
		if x % y == 0:
			return int(math.floor(x / y))
		return int(math.floor(x / y + self.repeatedSubtraction(y, x % y)))


class Solution:

	def repeatedSubtraction(self, A, B):
		n = 0
		while B != 0 and A != 0:
			if A > B:
				(A, B) = (B, A)
			n = n + B // A
			B = B % A
		return n


class Solution:

	def repeatedSubtraction(self, x, y):
		if x % y == 0:
			return x // y
		else:
			return x // y + self.repeatedSubtraction(y, x % y)


class Solution:

	def repeatedSubtraction(self, A, B):
		C = 0
		if B > A:
			C = B // A
			if B % A == 0:
				return C
			else:
				return C + self.repeatedSubtraction(A, B - C * A)
		else:
			C = A // B
			if A % B == 0:
				return C
			else:
				return C + self.repeatedSubtraction(A - C * B, B)


class Solution:

	def repeatedSubtraction(self, a, b):
		if a == 0 or b == 0:
			return 0
		if a < b:
			return b // a + self.repeatedSubtraction(a, b % a)
		else:
			return a // b + self.repeatedSubtraction(a % b, b)


class Solution:

	def repeatedSubtraction(self, A, B):
		if A % B == 0:
			return int(A // B)
		else:
			return int(A // B) + self.repeatedSubtraction(B, A % B)


class Solution:

	def repeatedSubtraction(self, A, B):

		def count(x, y):
			if x % y == 0:
				return x // y
			return x // y + count(y, x % y)
		return count(A, B)


class Solution:

	def repeatedSubtraction(self, A, B):

		def cool(a, b):
			if a % b == 0:
				return a // b
			elif b % a == 0:
				return b // a
			return 0
		if A == 0 or B == 0:
			return 0
		round = 0
		while A > 0 and B > 0:
			if A % B == 0:
				return round + A // B
			elif B % A == 0:
				return round + B // A
			if A < B:
				B -= A
			else:
				A -= B
			round += 1
		return round


class Solution:

	def repeatedSubtraction(self, A, B):
		if A == 0 or B == 0:
			return 0
		if A % B == 0:
			return int(A / B)
		return int(max(A, B) / min(A, B)) + self.repeatedSubtraction(min(A, B), max(A, B) % min(A, B))


class Solution:

	def modifiedGcd(self, A, B):
		if A % B == 0:
			return A // B
		return A // B + self.modifiedGcd(B, A % B)

	def repeatedSubtraction(self, A, B):
		return self.modifiedGcd(A, B)


class Solution:

	def repeatedSubtraction(self, a, b):
		ar = [a, b, max(a, b) - min(a, b)]
		count = 0
		while True:
			if a == 0 or b == 0:
				break
			tempa = a
			tempb = b
			a = min(tempa, tempb)
			b = max(tempa, tempb)
			count += b // a
			rem = b % a
			a = min(tempa, tempb)
			b = rem
		return count


class Solution:

	def repeatedSubtraction(self, A, B):
		if not A * B:
			return 0
		if A < B:
			A ^= B
			B ^= A
			A ^= B
		(a, b) = divmod(A, B)
		return a + self.repeatedSubtraction(b, B)