Vào một đêm không trăng, không sao, trong lúc muôn loài đang chìm vào giấc ngủ thì đột nhiên Giáo sư AliVu tỉnh dậy. Viết vội bài toán vừa gặp trong giấc mơ. Vì thấy bài toán hết sức thú vị nên vị Giáo sư để thức trắng cả đêm để giải mà vẫn không tài nào giải được. Nên Giáo sư AliVu đã quyết định nhờ đến sự giúp đỡ của bạn. Hãy giúp vị Giáo sư AliVu giải quyết cục tức này để có một giấc ngủ ngon lành.

Cho một dãy gồm ~n~ số nguyên dương ~a_1,a_2,\ldots,a_n~. Với mỗi vị trí ~i~, chỉ quan tâm đến những vị trí ~j~ đứng trước ~i~ và nguyên tố cùng nhau với ~i~, tức là ~j<i~ và ~\gcd(i,j)=1~.</p>

Mức độ liên quan giữa hai vị trí ~i~ và ~j~ được AliVu định nghĩa là ước chung lớn nhất của hai giá trị tại các vị trí đó: ~\gcd(a_i,a_j)~.

Với mỗi ~i~, đặt

$$ f(i) = \sum_{\substack{1\le j<i\\ \gcd(i,j)=1}} \gcd(a_i,a_j) $$ </p>

Nếu không tồn tại vị trí ~j~ thỏa mãn điều kiện trên thì ~f(i)=0~ .

AliVu muốn biết giá trị ~f(i)~ tại mọi vị trí trong dãy.

Hãy giúp Viết Minh tính ~f(1),f(2),\ldots,f(n)~.

Cấu hình Input

• Dòng đầu tiên chứa một số nguyên ~n~ ~(1\leq n\leq 2\cdot 10^5)~ — độ dài của dãy.
• Dòng thứ hai chứa ~n~ số nguyên dương ~a_1,a_2,\ldots,a_n~ ~(1\leq a_i\leq 2\cdot 10^5)~.

Cấu hình Output

• In ra ~n~ số nguyên, số thứ ~i~ là giá trị ~f(i)~.
• Các giá trị được ghi trên cùng một dòng.

Sample Input 1

5
6 10 15 9 21

Sample Output 1

0 2 8 6 10

Giải thích Sample 1

Với ~i=1~, không tồn tại ~j<i~, do đó ~f(1)=0~.</p>

Với ~i=2~, chỉ có ~j=1~ và ~\gcd(2,1)=1~,nên ~f(2)=\gcd(10,6)=2.~

Với ~i=3~, cả ~j=1~ và ~j=2~ đều nguyên tố cùng nhau với ~3~, do đó ~f(3) = \gcd(15,6)+\gcd(15,10) = 3+5 = 8.~

Với ~i=4~, các vị trí thỏa mãn là ~j=1~ và ~j=3~, vì ~\gcd(4,1)=\gcd(4,3)=1~. Do đó ~f(4) = \gcd(9,6)+\gcd(9,15) = 3+3 = 6.~

Với ~i=5~, cả bốn vị trí trước đó đều nguyên tố cùng nhau với ~5~, vì vậy

~\begin{aligned} f(5) &= \gcd(21,6) +\gcd(21,10) +\gcd(21,15) +\gcd(21,9)\\ &=3+1+3+3\\ &=10. \end{aligned} ~

Sample Input 2

6
12 12 12 12 12 12

Sample Output 2

0 12 24 24 48 24

Subtasks