Given a binary representation in the form of string(S) of a number n, the task is to find a binary representation of n+1.
Example 1:
Input: S = "10"
Output: 11
Explanation: "10" is the binary 
representation of 2 and binary 
representation of 3 is "11"
Example 2:
Input: S = "111"
Output: 1000
Explanation: "111" is the binary 
representation of 7 and binary 
representation of 8 is "1000"
Your Task:  
You don't need to read input or print anything. Complete the function binaryNextNumber()which takes S as input parameter and returns the string.
Expected Time Complexity:O(N)
Expected Auxiliary Space: O(N) to store resultant string  
Constraints:
1 <= N <= 10^{4}

Difficulty: EASY
Tags: Bit manipulation

Data structures
Skill types: Bit manipulation

Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N) to store resultant string

Starter code:
#User function Template for python3

class Solution:

	def binaryNextNumber(self, S):

		# code here

Solutions:
class Solution:

	def binaryNextNumber(self, S):
		return bin(int(S, 2) + 1)[2:]


class Solution:

	def binaryNextNumber(self, S):
		d = int(S, 2)
		d = d + 1
		return bin(d).replace('0b', '')


class Solution:

	def binaryNextNumber(self, S):
		l = len(S)
		num = list(S)
		flag = 0
		for i in range(l - 1, -1, -1):
			if num[i] == '0':
				num[i] = '1'
				flag = 1
				break
			else:
				num[i] = '0'
		res = ''.join(num)
		if flag == 0:
			res = '1' + res
		return res.lstrip('0')


class Solution:

	def binaryNextNumber(self, S):
		s = ''
		for i in range(len(S) - 1, -1, -1):
			if S[i] == '0':
				s = '1' + s
				s = S[:i] + s
				break
			else:
				s = '0' + s
		else:
			s = '1' + s
		for i in range(len(s)):
			if s[0] == '0':
				s = s[1:]
			else:
				break
		return s


class Solution:

	def binaryNextNumber(self, s):
		k = int(s, 2)
		n = k + 1
		s1 = bin(n)
		return s1[2:]


class Solution:

	def binaryNextNumber(self, s):
		l = int(s, 2)
		p = l + 1
		return bin(p)[2:]


class Solution:

	def binaryNextNumber(self, S):
		a = int(S, 2) + 1
		b = bin(a)
		b = str(b)
		return b[2:]


class Solution:

	def binaryNextNumber(self, S):
		return bin(eval('0b' + S) + 1)[2:]


class Solution:

	def binaryNextNumber(self, S):
		S = list(S)
		n = len(S)
		carry = '1'
		for i in range(n - 1, -1, -1):
			if S[i] == '1' and carry == '1':
				S[i] = '0'
			elif S[i] == '0' and carry == '1':
				S[i] = '1'
				carry = '0'
		if carry == '1':
			S.insert(0, '1')
		while S[0] == '0':
			S.pop(0)
		return ''.join(S)


class Solution:

	def binaryNextNumber(self, S):
		p = int(S, 2)
		q = p + 1
		r = bin(q).replace('0b', '')
		return r


class Solution:

	def binaryNextNumber(self, S):
		l = []
		flag = False
		for i in S:
			if i == '1':
				flag = True
			if flag:
				l.append(i)
		if len(l) == 0:
			l.append('0')
		count = 0
		for i in range(len(l) - 1, -1, -1):
			if l[i] == '0':
				l[i] = '1'
				break
			else:
				l[i] = '0'
		if l[0] == '0':
			l = ['1'] + l
		return ''.join(l)


class Solution:

	def binaryNextNumber(self, S):
		S = '0' + S
		ans = ''
		while len(S) > 0:
			if S[-1] == '1':
				ans = '0' + ans
			else:
				ans = '1' + ans
				S = S[:len(S) - 1]
				break
			S = S[:len(S) - 1]
		while len(S) > 0:
			ans = S[-1] + ans
			S = S[:len(S) - 1]
		while ans[0] == '0':
			ans = ans[1:]
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		S = input()
		ob = Solution()
		ans = ob.binaryNextNumber(S)
		print(ans)


class Solution:

	def binaryNextNumber(self, S):
		t = ''
		n = len(S)
		c = '1'
		for i in range(n - 1, -1, -1):
			if c == '1' and S[i] == '1':
				t = '0' + t
				c = '1'
			elif c == '1' and S[i] == '0':
				t = '1' + t
				c = '0'
			else:
				t = S[i] + t
		if c == '1':
			t = '1' + t
		return t.lstrip('0')
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		S = input()
		ob = Solution()
		ans = ob.binaryNextNumber(S)
		print(ans)


class Solution:

	def binaryNextNumber(self, S):
		return bin(int(S, 2) + 1)[2:]
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		S = input()
		ob = Solution()
		ans = ob.binaryNextNumber(S)
		print(ans)


class Solution:

	def binaryNextNumber(self, S):
		j = int(S, 2)
		l = str(bin(j + 1).replace('0b', ''))
		return l


class Solution:

	def binaryNextNumber(self, s):
		s = self.removeLeadingZeros(s)
		siz = len(s)
		if s[siz - 1] == '0':
			return s[0:siz - 1] + '1'
		previousBit = None
		hasFoundConsecutiveOnes = False
		countOnes = 0
		binaryStr = ''
		for i in reversed(range(siz)):
			currentBit = s[i]
			if currentBit == '1':
				countOnes += 1
			if previousBit == None:
				binaryStr = '0' + binaryStr
			elif hasFoundConsecutiveOnes == False:
				if previousBit != currentBit:
					hasFoundConsecutiveOnes = True
					binaryStr = '1' + binaryStr
				else:
					binaryStr = '0' + binaryStr
			else:
				binaryStr = currentBit + binaryStr
			previousBit = currentBit
		if siz == countOnes:
			return self.fillRightWithZero('1', siz)
		return binaryStr

	def removeLeadingZeros(self, s):
		if s[0] == '1':
			return s
		index = 0
		for i in range(len(s)):
			if s[i] == '1':
				index = i
				return s[index:]
		return '0'

	def fillRightWithZero(self, s, n):
		for i in range(n):
			s += '0'
		return s


class Solution:

	def binaryNextNumber(self, S):
		num = int(S, 2)
		res = num + 1
		str_res = ''
		while res != 0:
			if res & 1 == 1:
				str_res = '1' + str_res
			else:
				str_res = '0' + str_res
			res = res >> 1
		return str_res


class Solution:

	def binaryNextNumber(self, S):
		a = bin(int(S, 2) + 1)
		b = a.replace('0b', '')
		return b


class Solution:

	def binaryNextNumber(self, S):
		res = int(S, 2) + 1
		a = bin(res)[2:]
		return a


class Solution:

	def binaryNextNumber(self, S):
		k = int(S, 2)
		m = k + 1
		n = bin(m)[2:]
		return n


class Solution:

	def binaryNextNumber(self, S):
		t = int(S, 2)
		t1 = t + 1
		t2 = bin(t1)[2:]
		return t2


class Solution:

	def binaryNextNumber(self, S):
		dec = int(S, 2)
		dec += 1
		sum = bin(dec)
		final = sum.replace('0b', '')
		return final