Trong một buổi gặp mặt cuối năm, công ty tổ chức cho toàn thể nhân viên gặp mặt làm quen với nhau. Các nhân viên được đánh chỉ số từ ~1~ đến ~n~. Nhân viên thứ ~i~ nhận được mã số làm quen ~a_i~, các mã số không nhất thiết phân biệt. Toàn thể nhân viên xếp thành một vòng tròn theo chiều kim đồng hồ.

Lần lượt các nhân viên đi một vòng và bắt tay làm quen với những nhân viên khác có mã số là ước số của mã số nhân viên đó. Nhân viên thứ ~i~ bắt tay làm quen với nhân viên ~j~ nếu ~i~ khác ~j~ và ~a_i~ chia hết cho ~a_j~.

Hãy viết chương trình đếm tổng số lần bắt tay của mỗi nhân viên trong công ty sau khi kết thúc công việc làm quen.

Input

• Dòng đầu ghi số nguyên ~n~ ~(1 \le n \le 1000000)~;

• ~n~ dòng tiếp theo, dòng thứ ~i~ ghi số nguyên ~a_i~ ~(1 \le a_i \le 1000000)~.

Output

Ghi ~n~ dòng, dòng thứ ~i~ ghi số lần bắt tay của nhân viên thứ ~i~.

Scoring

Sample Input 1

5
2
1
2
3
4

Sample Output 1

2
0
2
1
3