Group the Integers

题号：NC217516
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

You need to divide all the integers ranging from 1 to $n$ (both inclusive) into some groups. The only constraint is that, the integers in the same group must be co-prime. Each integer must belong to exactly one group.

What's the smallest possible number of groups you can achieve?

输入描述:

There are multiple test cases. The first line of the input is an integer $T$ (about $10^5$ ), indicating the number of test cases. For each test case:

The first and only line contains an integer $n$ ( $1 \le n \le 10^9$ ).

输出描述:

    For each test case output one line containing one integer, indicating the smallest possible number of groups one can achieve.

示例1

输入

复制

2
2
5

输出

复制

1
2

说明

For the second sample test case, we can divide the integers into {1, 2, 3, 5} and {4}.