For a given string of binary number bi. Find the two’s complement of it.
Example 1:
Input: bi = 00000101
Output: 11111011
Explaination: 2's complement is reversing all 
the bits of the given number and then adding 
1 to it.
Example 2:
Input: bi = 101
Output: 011
Explaination: Follow the process of figuring 
out 2's complement. This will be the answer.
Your Task:
You do not need to read input or print anything. Your task is to complete the function complement() which takes bi as input parameter and returns the 2's complement of the number.
Expected Time Complexity: O(|bi|)
Expected Auxiliary Space: O(|bi|)
Constraints:
1 ≤ |bi| ≤ 10

Source: geeksforgeeks | Difficulty: EASY

Starter code: #User function Template for python3

class Solution:
    def complement(self, bi):
        # code here

Solutions:
class Solution:

	def complement(self, bi):
		bi = str(bi)
		reversebi = ''
		for i in bi:
			if i == '0':
				reversebi += '1'
			else:
				reversebi += '0'
		carry = 1
		twos_complement = ''
		for bit in reversebi[::-1]:
			if bit == '0' and carry == 1:
				twos_complement += '1'
				carry = 0
			elif bit == '1' and carry == 1:
				twos_complement += '0'
			else:
				twos_complement += bit
		return twos_complement[::-1]


class Solution:

	def complement(self, bi):
		an = ''
		for i in bi:
			if i == '0':
				an = an + '1'
			else:
				an = an + '0'
		n = int(an, 2) + 1
		b = bin(n)[2:]
		if len(bi) == len(b):
			return b
		elif len(bi) > len(b):
			for i in range(len(bi) - len(b)):
				b = '0' + b
			return b
		else:
			k = len(b) - len(bi)
			return b[k:]


class Solution:

	def complement(self, bi):
		ele = list(bi)
		for i in range(0, len(ele)):
			if ele[i] == '0':
				ele[i] = '1'
			else:
				ele[i] = '0'
		carry = 1
		for i in range(len(ele) - 1, -1, -1):
			if ele[i] == '1' and carry == 1:
				ele[i] = '0'
				carry = 1
			elif ele[i] == '0' and carry == 1:
				ele[i] = '1'
				carry = 0
		return ''.join(ele)


class Solution:

	def complement(self, bi):
		bi = list(bi)
		for i in range(len(bi)):
			if bi[i] == '0':
				bi[i] = '1'
			else:
				bi[i] = '0'
		i = len(bi) - 1
		while i >= 0:
			if bi[i] == '0':
				bi[i] = '1'
				break
			else:
				bi[i] = '0'
			i -= 1
		return ''.join(bi)


class Solution:

	def complement(self, bi):
		s = ''
		c = bi.count('0')
		if c == len(bi):
			return bi
		for i in bi:
			if i == '0':
				s += '1'
			elif i == '1':
				s += '0'
		if s[-1] == '0':
			a = s[0:len(s) - 1] + '1'
			return a
		s = s[-1::-1]
		a = ''
		b = 0
		for i in range(0, len(s)):
			if s[i] == '1':
				a += '0'
			elif s[i] == '0':
				a += '1'
				b = i
				break
		a += s[b + 1:len(s)]
		a = a[-1::-1]
		return a


class Solution:

	def complement(self, bi):
		ans = ''
		x = False
		for i in bi[::-1]:
			if x:
				if i == '0':
					ans += '1'
				else:
					ans += '0'
			else:
				ans += i
			if i == '1':
				x = True
		return ans[::-1]


class Solution:

	def complement(self, bi):
		bi = [str(1 - int(x)) for x in bi]
		k = len(bi) - 1
		while k >= 0:
			if bi[k] == '1':
				bi[k] = bi[k].replace('1', '0')
				k -= 1
			elif bi[k] == '0':
				bi[k] = bi[k].replace('0', '1')
				break
		return ''.join(bi)


class Solution:

	def complement(self, bi):
		x = ''
		for i in bi:
			if i == '1':
				x += '0'
			else:
				x += '1'
		x = list(x)
		i = len(x) - 1
		while i >= 0:
			if x[i] == '0':
				x[i] = '1'
				break
			else:
				x[i] = '0'
			i = i - 1
		return ''.join(map(str, x))
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		bi = input()
		ob = Solution()
		print(ob.complement(bi))


class Solution:

	def complement(self, bi):
		s = {'1': '0', '0': '1'}
		t = ''
		for i in bi:
			t += s[i]
		d = len(t) - 1
		c = 0
		for i in t:
			if i == '1':
				c += 2 ** d
			d -= 1
		c += 1
		s = bin(c)
		s = s[2:]
		if len(s) < len(t):
			s = '0' * (len(t) - len(s)) + s
		s = s[len(s) - len(t):]
		return s
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		bi = input()
		ob = Solution()
		print(ob.complement(bi))


class Solution:

	def complement(self, bi):
		s = ''
		n = len(bi)
		for i in bi:
			if i == '1':
				s += '0'
			elif i == '0':
				s += '1'
		one = list(s)
		two = list(one)
		for i in range(n - 1, -1, -1):
			if one[i] == '1':
				two[i] = '0'
			else:
				two[i] = '1'
				break
		i = i = 1
		if i == -1:
			two.insert(0, '1')
		s = ''
		for i in two:
			s += i
		return s


class Solution:

	def interchange(self, i):
		if i == '1':
			return '0'
		else:
			return '1'

	def complement(self, bi):
		l = list(map(self.interchange, bi))
		if l[-1] == '0':
			l[-1] = '1'
		else:
			l = l[::-1]
			for i in range(len(l)):
				if l[i] == '1':
					l[i] = '0'
				else:
					l[i] = '1'
					break
			l = l[::-1]
		return ''.join(l)


class Solution:

	def complement(self, bi):
		l = []
		for i in bi:
			if i == '0':
				l.append('1')
			else:
				l.append('0')
		if l[-1] == '0':
			l[-1] = '1'
		else:
			l = l[::-1]
			for i in range(len(l)):
				if l[i] == '1':
					l[i] = '0'
				else:
					l[i] = '1'
					break
			l = l[::-1]
		return ''.join(l)


class Solution:

	def complement(self, bi):
		l = len(bi)
		n = bin(2 ** l - int(bi, 2))[2:]
		length = len(n)
		if length > l:
			n = n[length - l:]
		return '0' * (l - len(n)) + n