For a given non-negative integer N, find the next smallest Happy Number. A number is called happy if it leads to 1 after a sequence of steps. Wherein at each step the number is replaced by the sum of squares of its digits that is if we start with Happy Number and keep replacing it with sum of squares of its digits, we reach 1 at some point. 
 
Example 1:
Input:
N = 8
Output:
10
Explanation:
Next happy number after 8 is 10 since
1*1 + 0*0 = 1
Example 2:
Input:
N = 10
Output
13
Explanation:
After 10, 13 is the smallest happy number because
1*1 + 3*3 = 10, so we replace 13 by 10 and 1*1 + 0*0 = 1.
Your Task:
You don't need to read input or print anything. Your task is to complete the function nextHappy() which takes an integer N as input parameters and returns an integer, next Happy number after N.
Expected Time Complexity: O(Nlog_{10}N)
Expected Space Complexity: O(1)
 
Constraints:
1<=N<=10^{5}

Difficulty: MEDIUM_HARD
Tags: Complete search
Skill types: Complete search
Expected Time Complexity: O(Nlog_{10}N)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3


class Solution:
    def nextHappy (self, N):
        # code here

Solutions:
class Solution:

	def SumSquare(self, n):
		summ = 0
		while n != 0:
			dg = n % 10
			summ += dg * dg
			n //= 10
		return summ

	def isHappy(self, n):
		st = set()
		st.add(n)
		while True:
			if n == 1:
				return 1
			n = self.SumSquare(n)
			if n in st:
				return 0
			st.add(n)
		return 0

	def nextHappy(self, N):
		for i in range(N + 1, N + 100):
			if self.isHappy(i):
				return i
		return -1


class Solution:

	def nextHappy(self, N):

		def ishappy(n, d):
			if n == 1:
				return True
			elif n in d:
				return False
			d[n] = 0
			a = str(n)
			m = 0
			for i in a:
				i = int(i)
				m = m + i * i
			return ishappy(m, d)
		d = {}
		for i in range(N + 1, 109990909):
			if ishappy(i, d):
				return i


class Solution:

	def nextHappy(self, N):

		def isHappy(n):
			l = [2, 3, 4, 5, 6, 8, 9]
			while n != 1:
				if n in l:
					return False
				s = 0
				for i in str(n):
					s += int(i) ** 2
				n = s
			return True
		x = N + 1
		while 1:
			if isHappy(x):
				return x
			x += 1


class Solution:

	def nextHappy(self, N):
		i = N + 1
		while True:
			if isHappy(i, set()):
				return i
			i += 1

def isHappy(N, s):
	s.add(N)
	a = N
	val = N
	while True:
		sum_ = 0
		while val != 0:
			k = val % 10
			val //= 10
			sum_ += k * k
		if sum_ == 1:
			return 1
		elif sum_ in s:
			return 0
		s.add(sum_)
		val = sum_


class Solution:

	def __init__(self):
		self.dp = {}

	def solve(self, n):
		if n == 1 or n == 7:
			return True
		elif n <= 9:
			return False
		ans = 0
		while n:
			d = n % 10
			ans += d * d
			n //= 10
		return self.solve(ans)

	def nextHappy(self, N):
		n = N + 1
		while True:
			if self.solve(n):
				return n
			n += 1
		return -1


def isHappy(n):
	k = n
	d = {}
	while True:
		try:
			if p[k]:
				return True
		except:
			pass
		s = 0
		try:
			return d[n]
		except:
			d[n] = False
		while n:
			s += (n % 10) ** 2
			n = n // 10
		n = s
		if n == 1:
			return True
	return True
p = {}
for i in range(1, 5 * 10 ** 4):
	p[i] = isHappy(i)

class Solution:

	def nextHappy(self, N):
		for i in range(N + 1, 5 * 10 ** 4):
			if p[i]:
				return i


class Solution:

	def nextHappy(self, N):

		def happy(n):
			s = 0
			while n:
				r = n % 10
				s += r * r
				n = n // 10
			return s

		def ishappy(n):
			s = set()
			while True:
				n = happy(n)
				if n == 1:
					return True
				if n in s:
					return False
				s.add(n)
		while True:
			N = N + 1
			if ishappy(N):
				return N


class Solution:

	def nextHappy(self, N):

		def ishappy(n):
			s = 0
			while n:
				r = n % 10
				s += r ** 2
				n = n // 10
			return s
		for i in range(N + 1, N + 100):
			t = i
			while i > 9:
				i = ishappy(i)
			if i == 1 or i == 7:
				return t
			else:
				continue


class Solution:

	def nextHappy(self, N):

		def fun(i):
			res = i
			while res != 1:
				i = res
				res = 0
				if a[i] == 0:
					a[i] = 1
					while i > 0:
						res += pow(i % 10, 2)
						i = i // 10
				else:
					return 0
			if res == 1:
				return 1
		a = [0] * 10000
		if N == 1:
			return 10
		for i in range(N + 1, 10000):
			res = fun(i)
			if res == 1:
				return i


class Solution:

	def nextHappy(self, N):

		def f(x):
			if x <= 10:
				if x == 1 or x == 7 or x == 10:
					return True
				return False
			s = 0
			while x > 0:
				v = x % 10
				s += v * v
				x //= 10
			return f(s)
		i = N + 1
		while True:
			if f(i):
				return i
			i += 1
		return -1


def happy(N):
	l = 0
	while N:
		r = N % 10
		l += r ** 2
		N = N // 10
		if l > 9 and N == 0:
			N = l
			l = 0
	if l == 1:
		return True
	return False

class Solution:

	def nextHappy(self, N):
		N = N + 1
		while happy(N) == False:
			N = N + 1
		return N


class Solution:

	def digits_N(self, N):
		num = N
		digits = []
		while num:
			digits.append(num % 10)
			num = num // 10
		return digits

	def check_happiness(self, N):
		num = N
		non_happy = []
		while num > 9:
			digits = self.digits_N(num)
			num = 0
			for i in digits:
				num += i * i
			if num in non_happy:
				return False
			non_happy.append(num)
		if num == 1:
			return True
		if num == 7:
			return True
		return False

	def nextHappy(self, N):
		happy_flag = False
		while not happy_flag:
			N = N + 1
			if self.check_happiness(N):
				happy_flag = True
		return N


class Solution:

	def isHappy(self, n):
		seen = set()
		while n not in seen:
			seen.add(n)
			n = sum((int(i) ** 2 for i in str(n)))
		return n == 1

	def nextHappy(self, N):
		N += 1
		while not self.isHappy(N):
			N += 1
		return N


class Solution:

	def nextHappy(self, N):
		i = N + 1
		while True:
			j = i
			l = []
			while True:
				if j in l:
					break
				if j == 1:
					return i
				sum = 0
				l.append(j)
				while j:
					sum += j % 10 * (j % 10)
					j //= 10
				j = sum
			i += 1


class Solution:

	def happy(self, n):
		s = set()
		while True:
			s.add(n)
			if n == 1:
				return True
			val = 0
			while n >= 1:
				val += (n % 10) ** 2
				n = n // 10
			n = val
			if n in s:
				return False

	def nextHappy(self, n):
		if self.happy(n + 1):
			return n + 1
		return self.nextHappy(n + 1)


def happy(n):
	temp = sum([pow(int(x), 2) for x in str(n)])
	d = {}
	d[temp] = 1
	if temp == 1:
		return True
	while True:
		temp = sum([pow(int(x), 2) for x in str(temp)])
		if d.get(temp) == None:
			d[temp] = 1
		else:
			return False
		if temp == 1:
			return True
	return False

class Solution:

	def nextHappy(self, N):
		N += 1
		while happy(N) != True:
			N += 1
		return N


class Solution:

	def nextHappy(self, N):

		def happy(n):

			def new(num):
				c = 0
				while num > 0:
					a = num % 10
					c += a ** 2
					num = num // 10
				return c
			slow = new(n)
			fast = new(new(n))
			while fast != slow and fast != 1 and (slow != 1):
				slow = new(slow)
				fast = new(new(fast))
			if fast == 1 or slow == 1:
				return True
			return False
		N = N + 1
		while True:
			if happy(N):
				return N
			N += 1


class Solution:

	def nextHappy(self, N):

		def dig(n):
			while n > 9:
				s = 0
				while n:
					t = n % 10
					s += t * t
					n //= 10
				n = s
			return n
		n = N + 1
		while True:
			if dig(n) == 1 or dig(n) == 7:
				return n
			n += 1


class Solution:

	def nextHappy(self, N):

		def fun(n):
			s = 0
			while n != 0:
				p = n % 10
				s = s + p * p
				n = n // 10
			return s
		for n in range(N + 1, N + 100):
			d = n
			while n > 9:
				n = fun(n)
			if n == 1 or n == 7:
				return d
			else:
				continue


class Solution:

	def check(self, n, l=[]):
		if n in l:
			return n == 1
		q = sum([int(x) ** 2 for x in str(n)])
		return self.check(q, [*l, n])

	def nextHappy(self, N):
		while True:
			N += 1
			if self.check(N):
				return N


class Solution:

	def sumofdigits(self, n):
		sum = 0
		while n != 0:
			r = n % 10
			n = n // 10
			sum = sum + r * r
		return sum

	def nextHappy(self, M):
		for n in range(M + 1, 50000):
			x = n
			while n > 9:
				n = self.sumofdigits(n)
			if n == 1 or n == 7:
				return x
				break


class Solution:

	def nextHappy(self, N):

		def happy(n):
			s = 0
			while n > 0:
				s += (n % 10) ** 2
				n //= 10
			if s == 1:
				return True
			if s == 4:
				return False
			return happy(s)
		i = N + 1
		while not happy(i):
			i += 1
		return i


class Solution:

	def square_sum(self, num):
		sqaure_sum1 = 0
		while num != 0:
			sqaure_sum1 += (num % 10) ** 2
			num //= 10
		return sqaure_sum1

	def check_indv_num(self, num):
		slow_ptr = num
		fast_ptr = num
		while True:
			slow_ptr = self.square_sum(slow_ptr)
			fast_ptr = self.square_sum(self.square_sum(fast_ptr))
			if slow_ptr == fast_ptr:
				break
		return slow_ptr == 1

	def nextHappy(self, N):
		for i in range(N + 1, N + 100):
			if self.check_indv_num(i):
				return i
		return -1


def sum_of_digits(n):
	s = 0
	while n > 0:
		s = s + (n % 10) ** 2
		n = n // 10
	return s

def is_happy_num(n):
	slow = n
	fast = sum_of_digits(n)
	while fast != 1 and slow != fast:
		slow = sum_of_digits(slow)
		fast = sum_of_digits(sum_of_digits(fast))
	if fast == 1:
		return True
	return False

class Solution:

	def nextHappy(self, N):
		n = N + 1
		while True:
			if is_happy_num(n):
				return n
			n += 1


class Solution:

	def nextHappy(self, N):

		def check(N):
			if N == 1 or N == 7:
				return True
			(sm, n) = (N, N)
			while sm > 9:
				sm = 0
				while n:
					re = n % 10
					sm += re * re
					n //= 10
				if sm == 1:
					return True
				n = sm
			if sm == 7:
				return True
			return False
		i = N + 1
		while True:
			if check(i):
				return i
			i += 1


class Solution:

	def isHappy(self, n):
		k = n
		while True:
			k = str(k)
			digitSqSum = 0
			for i in k:
				digitSqSum += int(i) * int(i)
			if digitSqSum == 1 or digitSqSum == 7:
				return True
			if digitSqSum < 10:
				return False
			if digitSqSum == n:
				return False
			k = digitSqSum

	def nextHappy(self, N):
		N += 1
		while not self.isHappy(N):
			N += 1
		return N


class Solution:

	def nextHappy(self, N):
		N += 1

		def ishappy(n):
			s = n
			while s > 9:
				s = 0
				while n > 0:
					r = n % 10
					s += r ** 2
					n //= 10
				if s > 9:
					n = s
			if s == 1 or s == 7:
				return True
			else:
				return False
		while 1:
			if ishappy(N):
				return N
				break
			N += 1


class Solution:

	def isHappy(self, N):
		if N == 1 or N == 7:
			return 1
		sum = N
		x = N
		while sum > 9:
			sum = 0
			while x > 0:
				d = x % 10
				sum += d * d
				x //= 10
			if sum == 1:
				return 1
			x = sum
		if sum == 7:
			return 1
		return 0

	def nextHappy(self, N):
		x = N + 1
		res = x
		while True:
			if self.isHappy(x):
				return x
			x += 1
			res = x
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nextHappy(N))


class Solution:

	def squaresum(self, n):
		s = 0
		while n != 0:
			s += n % 10 * (n % 10)
			n //= 10
		return s

	def nextHappy(self, N):
		n = N + 1
		while True:
			slow = n
			fast = n
			while True:
				slow = self.squaresum(slow)
				fast = self.squaresum(self.squaresum(fast))
				if slow != fast:
					continue
				else:
					break
			if slow == 1:
				return n
			n += 1
		return -1


class Solution:

	def nextHappy(self, n):
		q = {1: 1}
		s = set()

		def dfs(i):
			if i in q:
				return q[i]
			if i in s:
				return -1
			s.add(i)
			q[i] = dfs(sum((j * j for j in map(int, [*str(i)]))))
			return q[i]
		n += 1
		o = dfs(n)
		while o == -1:
			n += 1
			o = dfs(n)
		return n


from collections import defaultdict

class Solution:

	def nextHappy(self, N):
		stk = defaultdict(int)

		def R_happy(N):
			if N == 1:
				return True
			if N == 4:
				return False
			if stk[N]:
				return False
			sum_value = Summation(N)
			stk[N] = sum_value
			return R_happy(sum_value)

		def Summation(N):
			ans = 0
			while N:
				value = N % 10
				N = N // 10
				ans += value * value
			return ans
		for key in range(N + 1, 100000):
			if R_happy(key) == True:
				return key


class Solution:

	def nextHappy(self, N):
		N = N + 1
		while True:
			if self.ishappy(N):
				return N
			N += 1

	def ishappy(self, N):
		sum = 0
		while N > 0:
			digit = N % 10
			sum += digit * digit
			N = N // 10
		if sum == 1:
			return True
		if sum < 10:
			return False
		return self.ishappy(sum)


class Solution:

	def nextHappy(self, N):
		li = []
		for n in range(N, N + 100):
			p = n
			count_i = 0
			while n != 1:
				sum_i = 0
				for i in str(n):
					sum_i += int(i) ** 2
				n = sum_i
				count_i += 1
				if count_i > 10:
					break
			if n == 1:
				li.append(p)
		if li[0] == N:
			return li[1]
		else:
			return li[0]


class Solution:

	def nextHappy(self, N):

		def ha(n, l):
			l.append(n)
			if n == 1:
				return True
			s = 0
			while n:
				t = n % 10
				s += t * t
				n = int(n / 10)
			if s in l:
				return False
			return ha(s, l)
		N += 1
		while True:
			l = []
			if ha(N, l):
				return N
				break
			N += 1


class Solution:

	def nextHappy(self, N):
		dp = {}
		v = set()

		def f(i):
			if i in dp:
				return dp[i]
			if i == 1:
				dp[1] = True
				return True
			if i in v:
				dp[i] = False
				return False
			v.add(i)
			dp[i] = f(sum((int(j) ** 2 for j in str(i))))
			return dp[i]
		i = N + 1
		while True:
			if f(i):
				return i
			i += 1


class Solution:

	def nextHappy(self, N):

		def check(N):
			if N == 1 or N == 7:
				return True
			(sm, n) = (N, N)
			while sm > 9:
				sm = 0
				while n:
					re = n % 10
					sm += re * re
					n //= 10
				if sm == 1:
					return True
				n = sm
			if sm == 7:
				return True
			return False
		i = N + 1
		while True:
			if check(i):
				return i
			i += 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nextHappy(N))


class Solution:

	def nextHappy(self, N):
		while True:
			N += 1
			result = self.isHappy(N)
			if result:
				return N

	def isHappy(self, n):
		slow = self.squared(n)
		fast = self.squared(self.squared(n))
		while slow != fast and fast != 1:
			slow = self.squared(slow)
			fast = self.squared(self.squared(fast))
		return fast == 1

	def squared(self, n: int) -> int:
		res = 0
		while n > 0:
			digit = n % 10
			res += digit ** 2
			n = n // 10
		return res
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nextHappy(N))


class Solution:

	def nextHappy(self, N):

		def rec(n, dic):
			if n == 1:
				return True
			curr = 0
			while n != 0:
				temp = (n % 10) ** 2
				curr += temp
				n //= 10
			if curr in dic:
				return False
			dic.add(curr)
			return rec(curr, dic)
		while True:
			dic = set()
			if rec(N + 1, dic):
				return N + 1
			N += 1
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.nextHappy(N))


class Solution:

	def nextHappy(self, N):

		def numSquareSum(n):
			squareSum = 0
			while n:
				squareSum += n % 10 * (n % 10)
				n = int(n / 10)
			return squareSum

		def isHappynumber(n):
			slow = n
			fast = n
			while True:
				slow = numSquareSum(slow)
				fast = numSquareSum(numSquareSum(fast))
				if slow != fast:
					continue
				else:
					break
			return slow == 1
		while True:
			if isHappynumber(N + 1):
				return N + 1
			N += 1


class Solution:

	def checkHappyYear(self, N, loopCheck):
		if N == 1:
			return True
		s = 0
		while N != 0:
			s += (N % 10) ** 2
			N //= 10
		if s in loopCheck:
			return False
		loopCheck.add(s)
		return self.checkHappyYear(s, loopCheck)

	def solve(self, N):
		loopCheck = set([N])
		if self.checkHappyYear(N, loopCheck):
			return N
		return self.solve(N + 1)

	def nextHappy(self, N):
		return self.solve(N + 1)


class Solution:

	def isHappy(self, N):
		if N == 1 or N == 7:
			return 1
		sum = N
		x = N
		while sum > 9:
			sum = 0
			while x > 0:
				d = x % 10
				sum += d * d
				x //= 10
			if sum == 1:
				return 1
			x = sum
		if sum == 7:
			return 1
		return 0

	def nextHappy(self, N):
		x = N + 1
		res = x
		while True:
			if self.isHappy(x):
				return x
			x += 1
			res = x


def numSquareSum(n):
	squareSum = 0
	while n:
		squareSum += n % 10 * (n % 10)
		n = int(n / 10)
	return squareSum

def isHappynumber(n):
	st = set()
	while 1:
		n = numSquareSum(n)
		if n == 1:
			return True
		if n in st:
			return False
		st.add(n)

class Solution:

	def nextHappy(self, N):
		n = N + 1
		while True:
			if isHappynumber(n):
				return n
			n += 1


class Solution:

	def getSum(self, N):
		if N == 1 or N == 7 or N == 10:
			return True
		if N < 10:
			return False
		add = 0
		while N > 0:
			temp = N % 10
			add += temp * temp
			N = int(N / 10)
		return self.getSum(add)

	def nextHappy(self, N):
		while True:
			N = N + 1
			if self.getSum(N):
				return N


class Solution:

	def nextHappy(self, N):
		num = N + 1
		while True:
			isHappy = self.checkHappy(num)
			if isHappy:
				return num
			num += 1
		return None

	def checkHappy(self, n):
		seen = set()
		while True:
			n = self.getNextNumber(n)
			if n == 1:
				return True
			if n in seen:
				return False
			seen.add(n)
		return False

	def getNextNumber(self, n):
		total = 0
		while n > 0:
			rem = n % 10
			total += rem ** 2
			n = n // 10
		return total


class Solution:

	def nextHappy(self, N):

		def ishappy(n):
			temp = n
			a = 0
			while temp:
				r = temp % 10
				temp = temp // 10
				a += r * r
			if a > 9:
				return ishappy(a)
			if a == 1:
				return True
			return False
		i = N + 1
		while i:
			if ishappy(i):
				return i
			i += 1


class Solution:

	def nextHappy(self, N):
		n = N + 1

		def ishappy(n1, sq):
			while n1 != 0:
				rem = n1 % 10
				sq += rem * rem
				n1 = n1 // 10
				if n1 == 0:
					n1 = sq
					sq = 0
					if n1 >= 0 and n1 <= 9:
						break
			if n1 == 1:
				return True
			else:
				return False
		while n:
			n1 = n
			sq = 0
			if ishappy(n1, sq):
				return n
			else:
				n += 1


class Solution:
	count = True
	temp = 0
	status = False

	def nextHappy(self, N):
		if Solution.count:
			Solution.temp = N
			Solution.count = False
		n = str(N)
		t = 0
		if N == 7 and Solution.status == True:
			Solution.count = True
			Solution.status = False
			return Solution.temp
		for i in range(0, len(n)):
			t = t + int(n[i]) ** 2
		if t == 1 and Solution.status == True:
			Solution.count = True
			Solution.status = False
			return Solution.temp
		elif t >= 2 and t <= 9 and (t != 7) or (t == 1 and Solution.status == False):
			Solution.count = True
			Solution.status = True
			return self.nextHappy(Solution.temp + 1)
		else:
			return self.nextHappy(t)


from functools import reduce

class Solution:

	def nextHappy(self, N):

		def isHappy(n):
			arr = []
			while True:
				temp = list(map(int, str(n)))
				x = list(map(lambda x: x ** 2, temp))
				n = reduce(lambda x, y: x + y, x)
				if n == 1:
					return True
				if n in arr:
					return False
				arr.append(n)
		i = N + 1
		while True:
			if isHappy(i):
				return i
			i += 1


class Solution:

	def recur(self, num):
		if num == 1 or num == 7 or num == 10:
			return True
		if num < 10:
			return False
		sm = 0
		while num > 0:
			n = num % 10
			sm += n * n
			num //= 10
		return self.recur(sm)

	def nextHappy(self, N):
		number = N + 1
		while True:
			if self.recur(number):
				return number
			number += 1


from functools import reduce

class Solution:

	def nextHappy(self, N):

		def square(n):
			arr = list(map(int, str(n).strip()))
			temp = list(map(lambda x: x ** 2, arr))
			x = reduce(lambda x, y: x + y, temp)
			return x
		N = N + 1
		while True:
			n = N
			arr = [N]
			while True:
				n = square(n)
				if n == 1:
					return N
				if n in arr:
					break
				arr.append(n)
			N += 1


class Solution:

	def nextHappy(self, n):
		(p, b) = (0, 0)
		for i in range(n + 1, n + 50):
			if i == 1 or i <= 7:
				return 7
			else:
				b = self.check(i)
				if b == 1:
					return i

	def check(self, m):
		while m >= 10:
			k = [int(d) for d in str(m)]
			m = 0
			for i in k:
				m = m + i * i
		return m


class Solution:

	def nextHappy(self, N):
		hno = 0
		while hno != 1:
			N = N + 1
			l = list(str(N))
			hno = 0
			while hno >= 10 or hno == 0:
				sum1 = 0
				for i in l:
					sum1 = sum1 + int(i) ** 2
				hno = sum1
				l = list(str(sum1))
		return N


class Solution:

	def util(self, n):
		s = 0
		while n != 0:
			s += n % 10 * (n % 10)
			n = n // 10
		return s

	def nextHappy(self, N):
		i = N + 1
		while True:
			li = []
			s = i
			while 1:
				s = self.util(s)
				if s == 1:
					return i
				if s in li:
					break
				li.append(s)
			i += 1


class Solution:

	def ifhappy(self, num):
		s = 0
		for i in str(num):
			s += int(i) ** 2
		if s == 1 or s == 7:
			return 1
		elif len(str(s)) == 1:
			return 0
		return self.ifhappy(s)

	def nextHappy(self, N):
		i = 1
		while True:
			if self.ifhappy(N + i) == 0:
				i += 1
			else:
				break
		return N + i


class Solution:

	def nextHappy(self, N):
		for i in range(N + 1, 10000):
			if self.check(i):
				return i
		return -1

	def check(self, N):
		if N == 7 or N == 1 or N == 10:
			return True
		elif N < 10:
			return False
		sum = 0
		while N > 0:
			r = N % 10
			sum += r * r
			N = N // 10
		return self.check(sum)


class Solution:

	def nextHappy(self, N):
		memo = {}
		d = {}
		for i in range(10):
			d[i] = i * i

		def sol(cur, d):
			if cur == 1:
				return True
			temp = 0
			memo[cur] = False
			for i in str(cur):
				temp += d[int(i)]
			if temp not in memo:
				return sol(temp, d)
			else:
				return memo[temp]
		while True:
			N += 1
			if sol(N, d):
				return N


class Solution:

	def check(self, n):
		if n // 10 == 0:
			n = n % 10 * (n % 10)
		while n // 10 != 0:
			N = n
			nh = 0
			while N > 0:
				nh += N % 10 * (N % 10)
				N //= 10
			n = nh
		if n == 1:
			return 1
		else:
			return 0

	def nextHappy(self, N):
		if N == 0:
			return 1
		if self.check(N + 1):
			return N + 1
		else:
			return self.nextHappy(N + 1)


class Solution:

	def nextHappy(self, N):
		for j in range(N + 1, N ** 10):
			if j == 1 or j == 7:
				return j
			q = j
			while j > 9:
				i = 0
				x = str(j)
				z = 0
				while i < len(x):
					z = z + int(x[i]) ** 2
					i = i + 1
				if z == 1:
					return q
				j = z


class Solution:

	def isHappy(self, n):
		if n == 1 or n == 7:
			return True
		sos = n
		x = n
		while sos > 9:
			sos = 0
			while x > 0:
				d = x % 10
				sos += d * d
				x //= 10
			x = sos
		if sos == 1 or sos == 7:
			return True
		return False

	def nextHappy(self, N):
		n = N + 1
		while True:
			if self.isHappy(n):
				return n
			n += 1


class Solution:

	def check(self, n):
		if n in self.prev:
			return False
		self.prev.add(n)
		numbers = []
		while n:
			numbers.append(n % 10)
			n = n // 10
		ans = 0
		for i in numbers:
			ans += i * i
		if ans == 1:
			return True
		return self.check(ans)

	def nextHappy(self, N):
		i = N + 1
		while True:
			self.prev = set()
			if self.check(i):
				return i
			i += 1


class Solution:

	def isHappy(self, N):
		if N == 1 or N == 7:
			return True
		if N < 10:
			return False
		result = 0
		while N > 0:
			result += N % 10 * (N % 10)
			N = N // 10
		return self.isHappy(result)

	def nextHappy(self, N):
		N += 1
		while True:
			if self.isHappy(N):
				return N
			N += 1