K. Lonely Numberstime limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputIn number world, two different numbers are friends if they have a lot in common, but also each one has unique perks.More precisely, two different numbers a and b are friends if gcd(a,b), \frac{a}{gcd(a,b)}, \frac{b}{gcd(a,b)} can form sides of a triangle.Three numbers a, b and c can form sides of a triangle if a + b > c, b + c > a and c + a > b.In a group of numbers, a number is lonely if it doesn't have any friends in that group.Given a group of numbers containing all numbers from 1, 2, 3, ..., n, how many numbers in that group are lonely?InputThe first line contains a single integer t (1 \leq t \leq 10^6) - number of test cases.On next line there are t numbers, n_i (1 \leq n_i \leq 10^6) - meaning that in case i you should solve for numbers 1, 2, 3, ..., n_i.OutputFor each test case, print the answer on separate lines: number of lonely numbers in group 1, 2, 3, ..., n_i.ExampleInput
3
1 5 10
Output
1
3
3
NoteFor first test case, 1 is the only number and therefore lonely.For second test case where n=5, numbers 1, 3 and 5 are lonely.For third test case where n=10, numbers 1, 5 and 7 are lonely.
3
1 5 10

1 3 3 
['binary search', 'math', 'number theory', 'two pointers', '*1600']