Calculate the sum of all the multiples of 3 or 7 below the natural number N.
Example 1:
Input: 10
Output: 25
Explanation:
Numbers that are multiple of 3 or 7
are 3, 6, 7, 9 so sum will be 25.
Example 2:
Input: 25
Output: 84
Explanation: 
Numbers that are multiple of 3 or 7
are 3, 6, 7, 9, 12, 14, 15, 18 so 
sum will be 84.
Your Task:
You don't need to read or print anything. Your task is to complete the function sum() which takes N as input parameter and returns the sum of numbers that are multiple of 3 or 7.
Expected Time Complexity: O(1)
Expected Space Complexity: O(1)
Constraints:
1 <= N <= 1000000

Difficulty: EASY
Tags: Mathematics
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3

class Solution:
	def sum(self, N):
		# Code here

Solutions:
class Solution:

	def sum(self, N):
		s = 0
		for i in range(1, N):
			if i % 3 == 0 or i % 7 == 0:
				s += i
		return s


class Solution:

	def sum(self, N):
		(m3, m7, m21) = (N // 3, N // 7, N // 21)
		(s3, s7, s21) = (3 * (m3 * (m3 + 1) // 2), 7 * (m7 * (m7 + 1) // 2), 21 * (m21 * (m21 + 1) // 2))
		if N % 3 == 0 or N % 7 == 0:
			return s3 + s7 - N - s21
		return s3 + s7 - s21


class Solution:

	def sum(self, N):
		k = (N - 1) // 3
		m = (N - 1) // 7
		p = (N - 1) // 21
		S3 = 3 * (k * (k + 1) // 2)
		S7 = 7 * (m * (m + 1) // 2)
		S21 = 21 * (p * (p + 1) // 2)
		return S3 + S7 - S21


class Solution:

	def sum(self, N):
		l = []
		for i in range(N):
			if i % 3 == 0 or i % 7 == 0:
				l.append(i)
		return sum(l)


class Solution:

	def sum(self, N):
		s = set()
		a = 3
		for i in range(1, N):
			c = a * i
			if c >= N:
				break
			else:
				s.add(c)
		b = 7
		for i in range(1, N):
			d = b * i
			if d >= N:
				break
			else:
				s.add(d)
		ans = 0
		for i in s:
			ans += i
		return ans


class Solution:

	def sum(self, N):
		s = 0
		for x in range(0, N):
			if x % 3 == 0 or x % 7 == 0:
				s += x
		return s


class Solution:

	def sum(self, N):
		sum = 0
		for i in range(N):
			if i % 3 == 0 or i % 7 == 0:
				sum = sum + i
		return sum
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.sum(n)
		print(ans)


class Solution:

	def sum(self, n):
		n = n - 1
		x = 3
		n1 = n // 3
		s1 = n1 * (x + n1 * x) // 2
		y = 7
		n2 = n // 7
		s2 = n2 * (y + n2 * y) // 2
		z = 21
		n3 = n // 21
		s3 = n3 * (z + n3 * z) // 2
		ans = s1 + s2 - s3
		return ans
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.sum(n)
		print(ans)


class Solution:

	def sum(self, N):
		a = N - 1
		while a % 3 != 0:
			a = a - 1
		b = N - 1
		while b % 7 != 0:
			b = b - 1
		n3 = (a - 3) // 3 + 1
		n7 = (b - 7) // 7 + 1
		s3 = n3 * (6 + (n3 - 1) * 3) // 2
		s7 = n7 * (14 + (n7 - 1) * 7) // 2
		s21 = 0
		if N >= 21:
			c = N - 1
			while c % 21 != 0:
				c = c - 1
			n21 = (c - 21) // 21 + 1
			s21 = n21 * (42 + (n21 - 1) * 21) // 2
		return s3 + s7 - s21
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		ob = Solution()
		ans = ob.sum(n)
		print(ans)


class Solution:

	def sum(self, N):
		s = 0
		i = 1
		while i < N:
			if i % 3 == 0 or i % 7 == 0:
				s = s + i
			i += 1
		return s