Carrot

People say rabbits like carrots more than anything else. That is not true. Rabbits prefer leafy greens and grass, so eating carrots bores the warren, and the rabbits invented this game.

The game starts with $N$ carrots. The rabbits line up in order of cuteness. On its turn, a rabbit must split every remaining carrot into piles of equal size, using at least 2 piles and putting at least 2 carrots in each pile. A rabbit that manages the split eats 1 carrot. A rabbit that cannot split them eats 2 carrots. The one exception is a single remaining carrot: that rabbit eats only that one carrot.

The warren holds far more rabbits than carrots, and a rabbit always finds a valid split when one exists. The game runs until no carrot is left. How many rabbits eat a carrot?

The first line has the number of test cases $T$ ($1 \le T \le 10^6$).

Each of the next $T$ lines has one carrot count $N$ ($1 \le N \le 10^7$).

For each test case, print the number of rabbits that eat a carrot as a single integer on its own line.