You will be given a positive integer N. Your task is to find the number of positive integers K ≤ N such that K is not divisible by any number among the set {2,3,4,5,6,7,8,9,10}.
 
Example 1:
Input:
N = 11
Output:
2
Explanation:
1 and 11 are the only possible solutions.
Example 2:
Input:
N = 2
Output:
1
Explanation:
1 is the only possible solution.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function noOfNumbers() which takes an Integer N as input and returns the answer.
 
Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= N <= 10^{18}

Source: geeksforgeeks | Difficulty: EASY

Starter code: #User function Template for python3



class Solution:

    def noOfNumbers(self, N):

        # code here

Solutions:
class Solution:

	def noOfNumbers(self, N):
		a = N // 7 - N // 14 - N // 21 - N // 35 + N // 42 - N // 210 + N // 70 + N // 105
		b = N // 5 - N // 10 - N // 15 + N // 30
		c = N // 3 - N // 6
		d = N // 2
		return N - (a + b + c + d)


class Solution:

	def noOfNumbers(self, N):
		n = N
		return n - n // 2 - n // 3 - n // 5 - n // 7 + n // 6 + n // 10 + n // 14 + n // 15 + n // 21 + n // 35 - n // 30 - n // 42 - n // 70 - n // 105 + n // 210


class Solution:

	def noOfNumbers(self, n):
		count = 0
		c = n - (n // 2 + n // 3 + n // 5 + n // 7 - n // 6 - n // 10 - n // 14 - n // 15 - n // 21 - n // 35 + n // 30 + n // 42 + n // 70 + n // 105 - n // 210)
		return c


class Solution:

	def check(self, k):
		for i in [i for i in range(2, 11)]:
			if k % i == 0:
				return False
		return True

	def noOfNumbers(self, N):
		if N <= 10:
			return 1
		n = N
		return n - n // 2 - n // 3 - n // 5 - n // 7 + n // 6 + n // 10 + n // 14 + n // 15 + n // 21 + n // 35 - n // 30 - n // 42 - n // 70 - n // 105 + n // 210
		arr = [0 for i in range(0, N, 1)]
		arr[1] = 1
		arr[2] = 1
		arr[4] = 1
		arr[6] = 1
		ans = 0
		for j in range(1, N, 1):
			if 2 * (j + 1) - 1 < N:
				arr[2 * (j + 1) - 1] = 1
			if 3 * (j + 1) - 1 < N:
				arr[3 * (j + 1) - 1] = 1
			if 5 * (j + 1) - 1 < N:
				arr[5 * (j + 1) - 1] = 1
			if 7 * (j + 1) - 1 < N:
				arr[7 * (j + 1) - 1] = 1
		for j in range(0, N, 1):
			if arr[j] == 0:
				ans += 1
		return ans


class Solution:

	def noOfNumbers(self, N):
		if N < 10:
			return 1
		else:
			SET1 = N // 2 + N // 3 + N // 5 + N // 7 + N // 30 + N // 42 + N // 70 + N // 105
			SET2 = N // 6 + N // 10 + N // 14 + N // 15 + N // 21 + N // 35 + N // 210
			return N - SET1 + SET2


class Solution:

	def noOfNumbers(self, N):
		if N <= 10:
			return 1
		primes = [2, 3, 5, 7]
		union = N // 2 + N // 3 + N // 5 + N // 7 - N // 6 - N // 10 - N // 14 - N // 15 - N // 21 - N // 35 + N // 30 + N // 42 + N // 105 + N // 70 - N // 210
		return N - union


class Solution:

	def noOfNumbers(self, N):
		n = N
		return n - n // 2 - n // 3 - n // 5 - n // 7 + n // (2 * 3) + n // (3 * 5) + n // (5 * 7) + n // (7 * 2) + n // (2 * 5) + n // (3 * 7) - n // (2 * 3 * 5) - n // (3 * 5 * 7) - n // (5 * 7 * 2) - n // (3 * 7 * 2) + n // (2 * 3 * 5 * 7)


class Solution:

	def noOfNumbers(self, N):
		ans = N - N // 2 - N // 3 - N // 5 - N // 7 + N // (2 * 3) + N // (2 * 5) + N // (2 * 7) + N // (3 * 5) + N // (3 * 7) + N // (5 * 7) - N // (2 * 3 * 5) - N // (2 * 3 * 7) - N // (2 * 5 * 7) - N // (3 * 5 * 7) + N // (2 * 3 * 5 * 7)
		return ans


class Solution:

	def noOfNumbers(self, n):
		return n - n // 2 - n // 3 - n // 5 - n // 7 + n // 6 + n // 10 + n // 14 + n // 15 + n // 21 + n // 35 - n // 30 - n // 42 - n // 70 - n // 105 + n // 210
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.noOfNumbers(N))


import math

class Solution:

	def noOfNumbers(self, N):
		n = N
		if n <= 10:
			return 1
		else:
			return n - n // 2 - n // 3 - n // 5 - n // 7 + n // (2 * 3) + n // (2 * 5) + n // (2 * 7) + n // (3 * 5) + n // (3 * 7) + n // (5 * 7) - n // (2 * 3 * 5) - n // (2 * 3 * 7) - n // (2 * 5 * 7) - n // (3 * 5 * 7) + n // (2 * 3 * 5 * 7)


class Solution:

	def noOfNumbers(self, N):
		a = N // 2 + N // 3 + N // 5 + N // 7
		ab = N // 6 + N // 15 + N // 10 + N // 14 + N // 21 + N // 35
		abc = N // 30 + N // 42 + N // 70 + N // 105
		abcd = N // 210
		return N - (a - ab + abc - abcd)


class Solution:

	def noOfNumbers(self, N):
		sum = 0
		lookup = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 17, 17, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 24, 24, 24, 24, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 31, 31, 32, 32, 32, 32, 33, 33, 33, 33, 33, 33, 34, 34, 35, 35, 35, 35, 35, 35, 36, 36, 36, 36, 36, 36, 37, 37, 37, 37, 38, 38, 39, 39, 39, 39, 40, 40, 40, 40, 40, 40, 41, 41, 42, 42, 42, 42, 42, 42, 43, 43, 43, 43, 44, 44, 45, 45, 45, 45, 46, 46, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 48, 48]
		return N // 210 * lookup[210] + lookup[N % 210]


class Solution:

	def noOfNumbers(self, N):
		count = 0
		for i in [2, 3, 5, 7]:
			count += N // i
		for j in [6, 10, 14, 15, 21, 35]:
			count -= N // j
		for x in [30, 42, 70, 105]:
			count += N // x
		count -= N // (2 * 3 * 5 * 7)
		return N - count


class Solution:

	def noOfNumbers(self, N):
		total = 48 * (N // 210)
		N = N % 210
		for i in range(1, N + 1):
			if i % 2 != 0 and i % 3 != 0 and (i % 5 != 0) and (i % 7 != 0):
				total += 1
		return total


class Solution:

	def noOfNumbers(self, N):
		arr = [2, 3, 5, 7]
		ans = 0
		for i in range(1, 16):
			p = 1
			bitc = 0
			for j in range(4):
				if i & 1 << j:
					bitc += 1
					p = p * arr[j]
			if bitc & 1:
				ans += N // p
			else:
				ans -= N // p
		return N - ans