1241번 - 머리 톡톡

엄지 생일 기념으로 학생들은 파티를 하고 있다. 엄지는 N(1≤N≤100,000)명의 학생에게 1부터 N번까지 차례대로 번호를 부여하였고 그들을 순서대로 빙 둘러앉아 원을 만들게 하였다. (즉 i번째 학생은 i-1과 i+1학생 사이에 앉아있다. 단, N번째 학생은 N-1번째 학생과 첫 번째 학생 사이에 앉아있다.)

N명의 학생은 둘러앉아 "머리톡톡" 게임을 하려한다. 게임 규칙은 다음과 같다. 각각의 학생은 자신의 머리 위에 1,000,000 이하의 자연수 중 하나를 쓴다. 그리고 1번부터 N번 학생까지 한 명씩 차례대로 일어나 원을 돌면서 자신이 쓴 숫자가 다른 사람이 쓴 숫자의 배수이면 그 학생의 머리를 "톡톡" 친다.

문제는 각각의 학생이 일어나 자신의 자리로 돌아올 때까지 총 몇 명의 학생의 머리를 치는지 구하는 것이다.

첫째 줄에 학생의 수 N이 입력되고 다음 N개의 줄에는 1번부터 N번까지 각각의 학생이 자신의 머리에 쓴 숫자를 입력받는다.

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