당근

토끼가 당근을 가장 좋아한다는 말이 널리 퍼져 있지만 사실이 아니다. 토끼는 잎채소와 풀을 더 좋아한다. 그래서 당근만 먹는 일은 토끼 무리에게 지루하고, 무리는 다음 게임을 만들었다.

처음에 당근 $N$개가 있다. 토끼들은 귀여운 순서대로 줄을 서고, 자기 차례가 되면 남은 당근을 크기가 모두 같은 여러 무더기로 나눠야 한다. 무더기 수는 2 이상이어야 하고, 한 무더기에 들어가는 당근도 2개 이상이어야 한다. 이렇게 나눌 수 있으면 그 토끼는 당근을 1개 먹는다. 나눌 수 없으면 2개를 먹는다. 다만 남은 당근이 1개뿐이면 그 1개만 먹는다.

무리의 토끼 수는 당근 수보다 훨씬 많고, 나눌 방법이 있으면 토끼는 반드시 찾아낸다. 당근이 하나도 남지 않을 때까지 게임을 이어갈 때, 당근을 먹은 토끼는 몇 마리인가?

첫 줄에 테스트 케이스 수 $T$가 주어진다 ($1 \le T \le 10^6$).

이어지는 $T$개 줄에 각 테스트 케이스의 당근 개수 $N$이 한 줄에 하나씩 주어진다 ($1 \le N \le 10^7$).

테스트 케이스마다 당근을 먹은 토끼의 수를 정수 하나로 한 줄에 출력한다.