Statistics question: Sample size for a non-binary question?

Let’s say I have a website with 1,000,000 visitors a month. I want to track their clicks to better understand their behavior (nothing nefarious, just questions like “do they prefer the navigation buttons at the top or the links in the sidebar?”). If I can’t record all the visitors (too expensive), how do I determine a statistically appropriate sample size that can represent the behavior of the whole 1 million?

The sample size formulas I can find seem to be for yes/no questions, but when there are 500 possible things on the page for them to click on, how do I determine how many people I need in my sample?