Given N, find s such that sum of first s natural number is N.
 
Example 1:
Input: N = 10
Output: 4
Explanation: Sum of first 4 natural
number is 1 + 2 + 3 + 4 = 10.     
Example 2:
Input: N = 17
Output: -1
Explanaion: There is no such number.
 
Your Task:
You don't need to read or print anyhting. Your task is to complete the function find() which takes N as input parameter and returns s. If not possible return -1.
 
Expected Time Complexity: O(log(N))
Expected Space Complexity: O(1)
Constraints:
1 <= N <= 10^{9}

Source: geeksforgeeks | Difficulty: EASY

Starter code: #User function Template for python3

class Solution:
	def find(self, n):
		# Code here

Solutions:
class Solution:

	def find(self, n):
		m = 1
		summ = 0
		while n >= summ:
			summ += m
			if summ == n:
				return m
			else:
				m += 1
		return -1


class Solution:

	def find(self, n):
		s = c = 0
		i = 1
		while s < n:
			s += i
			c += 1
			i += 1
			if s == n:
				return c
		return -1


class Solution:

	def find(self, n):
		import sys
		sys.setrecursionlimit(10000000)
		i = 0
		i = self.Util(n, i)
		if i * (i + 1) // 2 == n:
			return i
		else:
			return -1

	def Util(self, n, i):
		if n <= 0:
			return i
		i = i + 1
		return self.Util(n - i, i)


class Solution:

	def find(self, n):
		c = 1
		while n > 0:
			n -= c
			c += 1
		if n == 0:
			return c - 1
		else:
			return -1


class Solution:

	def find(self, n):
		k = 0
		for i in range(1, n + 1):
			k = k + i
			if k == n:
				return i
				break
			elif k > n:
				return -1
				break


class Solution:

	def find(self, n):
		sum = 0
		i = 0
		while sum != n:
			sum += i
			if sum == n:
				return i
				break
			if sum > n:
				return -1
				break
			i += 1


class Solution:

	def find(self, n):
		_sum = 0
		s = 1
		while _sum < n:
			_sum += s
			s += 1
		s -= 1
		if _sum == n:
			return s
		return -1


class Solution:

	def find(self, n):
		i = 1
		total = 0
		while total < n:
			total += i
			i += 1
		if total != n:
			return -1
		return i - 1


import math

class Solution:

	def find(self, n):
		k = (-1 + math.sqrt(1 + 8 * n)) / 2
		if math.ceil(k) == math.floor(k):
			return math.ceil(k)
		else:
			return -1


class Solution:

	def find(self, n):
		sum = 0
		for i in range(0, n + 1):
			sum += i
			if sum == n:
				return i
			if sum > n:
				return -1
				break


class Solution:

	def find(self, n):
		if n == 1:
			return 1
		if n == 2:
			return -1
		for i in range(n):
			a = i * (i + 1) // 2
			if a == n:
				return i
			elif a > n:
				return -1
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.find(n)
		print(ans)


import math

class Solution:

	def find(self, n):
		ans = (math.sqrt(1 + 8 * n) - 1) / 2
		if ans == int(ans):
			return int(ans)
		return -1


import math

class Solution:

	def find(self, n):
		l = 0
		h = n // 2 + 1
		while l <= h:
			m = (l + h) // 2
			k = m * (m + 1) // 2
			if k == n:
				return m
			elif k < n:
				l = m + 1
			else:
				h = m - 1
		return -1


class Solution:

	def find(self, n):
		s = 0
		for i in range(1, n + 1):
			s = s + i
			if s == n:
				return i
			if s > n:
				return -1
		return -1


class Solution:

	def find(self, n):
		sum = 0
		if n < 0:
			return -1
		elif n == 1:
			return 1
		else:
			for i in range(1, n + 1):
				sum += i
				if sum >= n:
					return i if sum == n else -1


import sys
sys.setrecursionlimit(1000000000)

class Solution:

	def sum1(self, i, s, N):
		if s > N:
			return -1
		if s == N:
			return i - 1
		s = s + i
		return self.sum1(i + 1, s, N)

	def find(self, N):
		return self.sum1(1, 0, N)


class Solution:

	def find(self, n):
		s = 0
		count = 0
		for i in range(1, 10000000):
			if s == n:
				return count
			elif s > n:
				return -1
				break
			else:
				s += i
				count += 1


class Solution:

	def find(self, n):
		sumo = 1
		i = 1
		while sumo < n:
			i += 1
			sumo += i
		if sumo == n:
			return i
		return -1


class Solution:

	def find(self, s):
		l = 1
		r = int(s / 2) + 1
		while l <= r:
			mid = int((l + r) / 2)
			sum = int(mid * (mid + 1) / 2)
			if sum == s:
				return mid
			elif sum > s:
				r = mid - 1
			else:
				l = mid + 1
		return -1


class Solution:

	def find(self, n):
		sum_n = 0
		i = 1
		while sum_n != n and sum_n < n:
			sum_n += i
			i += 1
		if sum_n == n:
			return i - 1
		else:
			return -1