You are given queries. Each query consists of a single number . You can perform any of the operations on in each move:
1: If we take 2 integers and where , , then we can change
2: Decrease the value of by .
Determine the minimum number of moves required to reduce the value of to .
Input Format
The first line contains the integer .
The next lines each contain an integer, .
Constraints
Output Format
Output lines. Each line containing the minimum number of moves required to reduce the value of to .
Sample Input
2
3
4
Sample Output
3
3
Explanation
For test case 1, We only have one option that gives the minimum number of moves.
Follow -> -> -> . Hence, moves.
For the case 2, we can either go -> -> -> -> or -> -> -> . The 2nd option is more optimal. Hence, moves.