Given two binary strings A and B that represent value of two integers, find the product of two strings in Decimal Value.
 
Example 1:
Input:
A = "1100" , B = "01"
Output:
12
Explanation:
Decimal representation of A is 12 and
that of B is 1. So, A*B gives the
output 12.
Example 2:
Input:
A = "01" , B = "01"
Output:
1
Explanation:
Decimal representation of both A and 
B is 1. So, A*B gives the output 1.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function karatsubaAlgo() which takes Strings A and B as input and returns the answer.
 
Expected Time Complexity: O(Length of Binary String)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= |A|,|B| <= 25

Difficulty: EASY
Tags: String algorithms

Data structures

Divide and conquer
Skill types: Data structures
Expected Time Complexity: O(Length of Binary String)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

    def karatsubaAlgo(self, A , B):

        # code here 

Solutions:
class Solution:

	def karatsubaAlgo(self, A, B):
		a = int(A, 2)
		b = int(B, 2)
		c = a * b
		return c


class Solution:

	def karatsubaAlgo(self, A, B) -> int:
		x = int(A, 2)
		y = int(B, 2)
		return x * y


class Solution:

	def karatsubaAlgo(self, A, B):
		m = int(A, 2)
		n = int(B, 2)
		return m * n


class Solution:

	def karatsubaAlgo(self, A, B):
		return int(A, 2) * int(B, 2)


class Solution:

	def karatsubaAlgo(self, A, B):
		n1 = int(A, 2)
		n2 = int(B, 2)
		return n1 * n2


class Solution:

	def karatsubaAlgo(self, A, B):
		d = int(A, 2)
		e = int(B, 2)
		return d * e


class Solution:

	def karatsubaAlgo(self, A, B):
		p = int(A, 2)
		q = int(B, 2)
		return p * q


class Solution:

	def karatsubaAlgo(self, A, B):
		m = int(A, 2)
		m1 = int(B, 2)
		return m * m1


class Solution:

	def karatsubaAlgo(self, A, B):

		def BinToInt(n):
			ans = 0
			k = 0
			for i in n[::-1]:
				ans += int(i) * 2 ** k
				k += 1
			return ans
		return BinToInt(A) * BinToInt(B)


class Solution:

	def karatsubaAlgo(self, A, B):
		s = int(A, 2)
		d = int(B, 2)
		return s * d


class Solution:

	def toInt(self, s):
		ans = 0
		for c in s:
			ans = (ans << 1) + (c == '1')
		return ans

	def karatsubaAlgo(self, A, B):
		A = self.toInt(A)
		B = self.toInt(B)
		return A * B


import numpy as np

class Solution:

	def karatsubaAlgo(self, A, B):
		a = int(A, 2)
		b = int(B, 2)
		c = a * b
		return c


class Solution:

	def karatsubaAlgo(self, A, B):
		c = int(A, 2)
		d = int(B, 2)
		return c * d


class Solution:

	def karatsubaAlgo(self, A, B):
		A1 = int(A, 2)
		B1 = int(B, 2)
		return A1 * B1


class Solution:

	def karatsubaAlgo(self, A, B):
		decA = int(A, 2)
		decB = int(B, 2)
		p = decA * decB
		return p


class Solution:

	def karatsubaAlgo(self, A, B):
		s1 = 0
		s2 = 0
		l1 = len(A) - 1
		l2 = len(B) - 1
		for i in range(len(A)):
			if A[l1] == '1':
				s1 = s1 + 2 ** i
				l1 = l1 - 1
			else:
				l1 = l1 - 1
		for i in range(len(B)):
			if B[l2] == '1':
				s2 = s2 + 2 ** i
				l2 = l2 - 1
			else:
				l2 = l2 - 1
		return s1 * s2


class Solution:

	def karatsubaAlgo(self, A, B):
		return self.convertBinary(A) * self.convertBinary(B)

	def convertBinary(self, s):
		num = 0
		pow_num = 0
		for i in range(len(s) - 1, -1, -1):
			num += int(s[i]) * pow(2, pow_num)
			pow_num += 1
		return num


class Solution:

	def getdec(self, binary):
		dec = 0
		j = 0
		n = len(binary)
		for i in range(n - 1, -1, -1):
			dec += int(binary[i]) * 2 ** j
			j += 1
		return dec

	def karatsubaAlgo(self, A, B):
		p1 = self.getdec(A)
		p2 = self.getdec(B)
		return p1 * p2


class Solution:

	def karatsubaAlgo(self, A, B):
		A = A.lstrip('0')
		B = B.lstrip('0')
		d = len(A) - 1
		c = 0
		for i in A:
			if i == '1':
				c += 2 ** d
			d -= 1
		d = len(B) - 1
		e = 0
		for i in B:
			if i == '1':
				e += 2 ** d
			d -= 1
		return e * c


class Solution:

	def karatsubaAlgo(self, A, B):
		return int(A, 2) * int(B, 2)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(A, B) = map(str, input().split())
		ob = Solution()
		print(ob.karatsubaAlgo(A, B))


class Solution:

	def dec(self, n):
		n = int(n)
		res = 0
		i = 0
		while n != 0:
			d = n % 10
			res = res + d * 2 ** i
			n //= 10
			i += 1
		return res

	def karatsubaAlgo(self, A, B):
		a = self.dec(A)
		b = self.dec(B)
		return a * b
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(A, B) = map(str, input().split())
		ob = Solution()
		print(ob.karatsubaAlgo(A, B))


class Solution:

	def karatsubaAlgo(self, A, B):
		s1 = 0
		s2 = 0
		for i in range(len(A)):
			s1 += int(2 ** i * int(A[len(A) - i - 1]))
		for j in range(len(B)):
			s2 += int(2 ** j * int(B[len(B) - j - 1]))
		return int(s1 * s2)


class Solution:

	def karatsubaAlgo(self, A, B):
		(a, b) = (0, 0)
		for i in range(len(A)):
			a *= 2
			if A[i] == '1':
				a += 1
		for i in range(len(B)):
			b *= 2
			if B[i] == '1':
				b += 1
		return a * b


class Solution:

	def convertToDecimal(self, x):
		if x == 1 or x == 0:
			return x
		l = len(str(x))
		firstDigit = x // pow(10, l - 1)
		return pow(2, l - 1) * firstDigit + self.convertToDecimal(x % pow(10, l - 1))

	def karatsubaAlgo(self, A, B):
		answerA = self.convertToDecimal(int(A))
		answerB = self.convertToDecimal(int(B))
		return answerA * answerB


class Solution:

	def karatsubaAlgo(self, A, B):

		def dec(A):
			ans = 0
			for i in range(len(A)):
				if A[-i - 1] == '1':
					ans += 2 ** i
			return ans
		return dec(A) * dec(B)


class Solution:

	def karatsubaAlgo(self, a, b):
		a = int(a)
		b = int(b)
		s1 = 0
		i = 0
		while a > 0:
			d = a % 10
			s1 += d * pow(2, i)
			i += 1
			a = a // 10
		s2 = 0
		i = 0
		while b > 0:
			d = b % 10
			s2 += d * pow(2, i)
			i += 1
			b = b // 10
		return s1 * s2


class Solution:

	def karatsubaAlgo(self, A, B):
		A = A[::-1]
		B = B[::-1]
		a = 0
		b = 0
		for i in range(len(A)):
			a += int(A[i]) * pow(2, i)
		for j in range(len(B)):
			b += int(B[j]) * pow(2, j)
		return a * b


import math

class Solution:

	def karatsubaAlgo(self, A, B):
		A_base10 = 0
		B_base10 = 0
		for (j, i) in enumerate(A[::-1]):
			A_base10 = A_base10 + int(i) * int(math.pow(2, j))
		for (j, i) in enumerate(B[::-1]):
			B_base10 = B_base10 + int(i) * int(math.pow(2, j))
		return A_base10 * B_base10


class Solution:

	def getDecimal(self, string):
		n = len(string)
		val = 0
		ml = 1
		for i in range(n - 1, -1, -1):
			if string[i] == '1':
				val += ml
			ml *= 2
		return val

	def karatsubaAlgo(self, A, B):
		return self.getDecimal(A) * self.getDecimal(B)


class Solution:

	def karatsubaAlgo(self, a, b):
		p1 = 0
		p2 = 0
		k = 1
		for i in a[::-1]:
			if i == '1':
				p1 += k
			k *= 2
		k = 1
		for i in b[::-1]:
			if i == '1':
				p2 += k
			k *= 2
		return p1 * p2


class Solution:

	def karatsubaAlgo(self, A, B):
		A10 = int(A, 2)
		B10 = int(B, 2)
		return A10 * B10


class Solution:

	def karatsubaAlgo(self, A, B):
		value_b = 0
		value_a = 0
		for (index, value) in enumerate(A):
			r_index = len(A) - index - 1
			value_a = value_a + 2 ** r_index * int(value)
		for (index, value) in enumerate(B):
			r_index = len(B) - index - 1
			value_b = value_b + 2 ** r_index * int(value)
		return value_a * value_b


class Solution:

	def karatsubaAlgo(self, A, B):
		(decimal1, decimal2, power) = (0, 0, 0)
		(A, B) = (int(A), int(B))
		while A > 0:
			(A, rem) = divmod(A, 10)
			rem = rem * 2 ** power
			decimal1 += rem
			power += 1
		power = 0
		while B > 0:
			(B, rem) = divmod(B, 10)
			rem = rem * 2 ** power
			decimal2 += rem
			power += 1
		return decimal1 * decimal2


class Solution:

	def karatsubaAlgo(self, A, B):
		a = len(A)
		b = len(B)
		num1 = 0
		num2 = 0
		j = max(a, b)
		B = B.zfill(j)
		A = A.zfill(j)
		os = j - 1
		for i in range(j):
			num1 = num1 + int(A[i]) * 2 ** os
			num2 = num2 + int(B[i]) * 2 ** os
			os = os - 1
		return num1 * num2


class Solution:

	def karatsubaAlgo(self, A, B):
		num = 0
		base = 1
		n = len(A)
		for i in range(n - 1, -1, -1):
			if A[i] == '1':
				num += base
			base *= 2
		res = 0
		m = len(B)
		for j in range(m - 1, -1, -1):
			if B[j] == '1':
				res = res + (num << m - 1 - j)
		return res


class Solution:

	def karatsubaAlgo(self, A, B):
		x = 0
		x1 = 0
		t = 0
		for i in range(len(A) - 1, -1, -1):
			if A[i] == '0':
				t += 1
				continue
			else:
				x = x + 2 ** t
				t += 1
		t = 0
		for i in range(len(B) - 1, -1, -1):
			if B[i] == '0':
				t += 1
				continue
			else:
				x1 = x1 + 2 ** t
				t += 1
		return x * x1


class Solution:

	def karatsubaAlgo(self, A, B):
		s1 = 0
		l1 = len(A)
		i = l1 - 1
		x = 1
		y = 1
		while i >= 0:
			if A[i] != '0':
				s1 = s1 + int(A[i]) * x
			x = x * 2
			i = i - 1
		l2 = len(B)
		j = l2 - 1
		s2 = 0
		while j >= 0:
			if B[j] != '0':
				s2 = s2 + int(B[j]) * y
			j = j - 1
			y = y * 2
		return s2 * s1


class Solution:

	def to_deci(self, n):
		s = 0
		for (i, d) in enumerate(reversed(n)):
			s += 2 ** i * (d == '1')
		return s

	def karatsubaAlgo(self, A, B):
		da = self.to_deci(A)
		db = self.to_deci(B)
		return da * db


class Solution:

	def karatsubaAlgo(self, a, b):
		return int(str(a), 2) * int(str(b), 2)


class Solution:

	def karatsubaAlgo(self, A, B):
		x = 0
		ans = 0
		n1 = len(A)
		n2 = len(B)
		for i in range(n1):
			if A[i] == '1':
				x += pow(2, n1 - 1 - i)
		for i in range(n2):
			if B[i] == '1':
				ans += x << n2 - 1 - i
		return ans


class Solution:

	def getInt(self, n):
		ind = 0
		sum = 0
		while n > 0:
			k = n % 10
			if k == 1:
				sum += pow(2, ind)
			ind += 1
			if len(str(n)) > 1:
				n = int(str(n)[:-1])
			else:
				n = 0
		return sum

	def karatsubaAlgo(self, A, B):
		a = self.getInt(int(A))
		b = self.getInt(int(B))
		return a * b