머리 톡톡

엄지의 생일을 맞아 학생들이 파티를 하고 있다. 엄지는 학생 N명에게 1번부터 N번까지 번호를 붙이고, 번호 순서대로 원형으로 둘러앉게 했다. 즉, i번 학생은 i-1번 학생과 i+1번 학생 사이에 앉으며, N번 학생은 N-1번 학생과 1번 학생 사이에 앉는다.

이제 학생들은 "머리 톡톡" 게임을 한다. 각 학생은 1,000,000 이하의 자연수 하나를 자기 머리 위에 쓴다. 그런 다음 1번 학생부터 N번 학생까지 차례대로 일어나 원을 한 바퀴 돈다. 어떤 학생이 쓴 수가 다른 학생이 쓴 수의 배수라면, 일어난 학생은 그 다른 학생의 머리를 한 번 친다.

각 학생에 대해, 그 학생이 일어나 자기 자리로 돌아올 때까지 머리를 치는 학생 수를 구하라. 같은 수를 쓴 학생이 여러 명이면 각각을 별개의 학생으로 센다. 단, 자기 자신의 머리는 치지 않는다.

첫째 줄에 학생의 수 N이 주어진다. (1 <= N <= 100,000)

다음 N개의 줄에는 1번 학생부터 N번 학생까지 각 학생이 머리에 쓴 자연수가 차례대로 주어진다. 각 수는 1,000,000 이하이다.

총 N개의 줄을 출력한다. i번째 줄에는 i번 학생이 원을 한 바퀴 돌면서 머리를 치는 학생 수를 출력한다.