Carrot

Time limit1sMemory limit256 MB

Summary

For each N, count the steps to reach zero by subtracting one when the pile splits into equal piles of at least two and subtracting two otherwise.

Level: Medium5 of 10
Topics: Number theory, Dynamic programming
Solved: No attempts yet

Problem

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?

Input

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$ ).

Output

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

Examples2

Example 1
Input
```
3
1
10
100
```
Expected output
```
1
7
76
```

Example 2

Input

Expected output