Each of the 1000 gnomes has a hat, blue on the outside and red on the inside (or vice versa). If a gnome is wearing the red hat, he can only lie, and if he is wearing the blue hat, he can only tell the truth. Throughout one day, each gnome told every other gnome, "You are wearing a red hat!" (some gnomes turned their hats inside out during the day). Find the minimum possible number of times the hats were turned inside out. (I. Bogdanov)