Problem C
Sequence

A sequence of positive integers $(x_1,\dots ,x_m)$ is good if $x_1=1$ and for each $1<j\le m$ we have either $x_j=x_{j-1}+1$ or $x_j=x_k\cdot x_l$ for some $k$ and $l$ with $0<k\le l<j$. For instance, the sequences $(1,1)$ and $(1,2)$ are both good, but the sequence $(1,3)$ is not good. For $n$ given integers $w_1,\dots ,w_n$ define the weight of an integer sequence $(x_1,\dots ,x_m)$ satisfying $1\le x_j\le n$ for each $1\le j\le m$ as

For instance, given the weights $w_1=10,w_2=42,w_3=1$, the weight of the sequence $(1,1)$ is $20$ and the weight of the sequence $(1,3)$ is $11$. For $1\le v\le n$, define $s_v$ as the smallest possible weight of a good sequence containing the value $v$.

Your task is to determine the values $s_1,\dots ,s_n$.

Input

The first line of input consists of the integer $n$, the number of weights. The next $n$ lines contain the integer weights $w_1,\dots ,w_n$.

Output

Print $n$ lines containing $s_1$, $\dots$, $s_n$ in order.

Constraints and Scoring

We always have $1\le n\le 30000$ and $1\le w_i\le {10}^6$ for each $1\le i\le n$.

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

3
10
42
1

10
52
53