In a small Scottish town stood a school where exactly 1000 students studied. Each of them had a locker for their clothes - a total of 1000 lockers, numbered from 1 to 1000. And in this school lived ghosts - exactly 1000 ghosts. Every student, leaving the school, locked their locker, and at night the ghosts began to play with the lockers, either unlocking or locking them. One evening, as usual, the students left all the lockers locked. At midnight, the ghosts appeared. First, the first ghost
unlocked all the lockers; then the second ghost locked the lockers whose numbers were divisible by 2; then the third ghost changed the positions (that is, unlocked the locker if it was locked, and locked it if it was unlocked) of the lockers whose numbers were divisible by 3; then the fourth ghost changed the positions of the lockers whose numbers were divisible by 4, and so on. As soon as the thousandth ghost changed the position of the thousandth locker, the rooster crowed, and all the ghosts hurried back to their hiding places. Can you tell how many lockers remained open after the ghosts' visit?
If the cabinet number $C$ is not a perfect square, then it has an even number of divisors (see problem 30365). Such a cabinet will change positions an even number of times and will end up closed. If, however, the cabinet number $C$ is a perfect square, then the number of its distinct divisors will be odd, and the cabinet will end up open. The number of perfect squares among the first thousand numbers is 31. Therefore, there will be 31 open cabinets.

## Answer

31 cabinets.