베시의 생일날 파티 게임을 할 시간이다.

베시는 N 마리의 소들을 차례대로 1 , 2 , 3 , ... , N (1 <= N <= 100,000) 번의 번호를 부여하고 , 원형으로 앉게 했다. 즉 i 번째 소 옆에는 i-1 번째 i+1 번째 소가 위치하고 있고 , N 번째 소 옆에는 1 번째 소가 있다.

농부 존은 번호가 1 에서 1,000,000 이 적힌 종이 10 억개를 통에 채웠다.

돌아 가면서, i 번째 소는 이 통에서 수 A_i ( 1 <= A_i <= 1 000 000 )의 종이를 뽑는다(반드시 유일할 필요는 없다)

모든 소들은 원 주위를 한 바뀌 돌면서 A_i 가 A_j 의 약수이면 j 번째 소의 머리를 때린후 원 위치한다. 모든 소들이 다른 소를 때리는 횟수를 출력하는 것이 일이다.

제한시간은 2 초이다.

입력

출력

입출력 예

입력

5
2
1
2
3
4

출력

2
0
2
1
3

입출력 예의 보충

첫 번째 소가 두 번째 , 세 번째 소를 때릴 수 있고 , 두 번째 소는 때릴 소가 없고....

출처:usaco