KöMaL 2007 K126

There are one thousand rooms in the sultan's palace. In each room there is a switch that switches all the lamps in the room on or off. When the lamps were on in each room and the sultan was bored, he walked through all his rooms one by one and repeated his walk again and again, always starting with the first room. During the first walk, he turned all the switches. The second time he turned the switch in every second room. The third time he turned the switch in every third room, and so on. (He turned the light on if it was off, and he turned it off if it was on). When he had walked through his room 500 times, he got tired of the game and decided to go to bed. He needed a room in which the lights were off. Which rooms did he have to choose from?