Vào các ngày cuối tuần, shiba sẽ dành thời gian ngồi xem phim cùng với người yêu của mình.

Người yêu của shiba đã quyết định sẽ xem một danh sách các bộ phim gồm \(n\) bộ phim, bộ phím thứ \(i\) có thời lượng là \(a_i\) phút. Tuy nhiên, việc xem phim lâu dễ gây ra nhàm chán. Chính vì thế, shiba mới quyết định "bật nóc", đổi một vài bộ phim theo ý của mình.

Phim không nhàm chán, nhưng thời lượng phim thì rất nhàm chán. Một dãy các bộ phim liên tiếp được gọi là nhàm chán nếu như ước chung lớn nhất của thời lượng các bộ phim đó bằng đúng số lượng bộ phim trong dãy đó. Nói cách khác, một dãy các bộ phim liên tiếp từ \(l\) đến \(r\) được gọi là nhám chán nếu \(gcd(a_l, a_{l+1}, a_{l+2},..., a_{r}) = r - l +1\). Để bớt nhàm chán, shiba có quyền đổi thời lượng của một bộ phim bất kì thành một bộ phim khác có thời lượng bất kì. Nói cách khác, shiba được quyền chọn bộ phim thứ \(i\) và một bộ phim khác có thời lượng là \(t\), sau đó gán cho bộ phim thứ \(i\) có thời lượng là \(t\). Việc thực hiện thay đổi bộ phim ở tuần thứ \(x\) chỉ có tác dụng ở tuần đó, các tuần khác không bị ảnh hưởng.

Việc xem phim được chia làm \(n\) tuần. Vào tuần thứ nhất, shiba sẽ xem \(1\) bộ phim, là bộ phim có thời lượng \(a_1\). Vào tuần thứ hai, shiba sẽ xem \(2\) bộ phim, là các bộ phim có thời lượng \(a_1, a_2\). Cứ như vậy, vào tuần thứ \(k\), shiba sẽ xem \(k\) bộ phim, là các bộ phim có thời lượng \(a_1, a_2,..., a_k\).

Yêu cầu: Hỏi với mỗi tuần, shiba phải thay đổi ít nhất bao nhiêu bộ phim để danh sách phim của cậu ấy không bị nhàm chán?

Input

• Dòng thứ nhất chứa một số nguyên dương \(n\) (\(n \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên dương \(a_1, a_2,... a_n\) (\(a_i \le 10^9\)).

Output

• Gồm một dòng chứa \(n\) số nguyên, số nguyên thứ \(i\) là số lượng bộ phim phải đổi ít nhất trong tuần thứ \(i\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 10^3\).
• Subtask \(3\) (\(60\%\) số điểm): không có giới hạn gì thêm.

Example

1
1

1