Head Taps

Students are having a party for Eomji's birthday. Eomji numbers N students from 1 to N and seats them around a circle in that order. In other words, student i sits between students i-1 and i+1, and student N sits between student N-1 and student 1.

The students will now play a game called "Head Taps". Each student writes one positive integer not greater than 1,000,000 above their head. Then, from student 1 through student N, each student stands up in order and walks once around the circle. If the number written by the standing student is a multiple of the number written by another student, the standing student taps that other student's head once.

For each student, determine how many students' heads they tap before returning to their seat. If several students wrote the same number, count them as separate students. A student does not tap their own head.

The first line contains the number of students N. (1 <= N <= 100,000)

Each of the next N lines contains the positive integer written by one student, in order from student 1 to student N. Each number is at most 1,000,000.

Print N lines. The i-th line must contain the number of students whose heads student i taps while walking once around the circle.