COVID tests

Adam's school has a new wave of the COVID epidemic. To prevent further spread, the school has decided to test all students with antigen tests using saliva samples.

Since all teachers forgot how to use the tests long ago, Adam signed up as a volunteer to help with testing.

Adam received saliva samples from $N$ students. For privacy reasons, he may only know the identifiers $0$ to $N-1$. His task is to find out which samples are positive. Testing every sample one by one is long and tedious. Instead, he can mix a subset of samples and test the mix. The test tells him whether all samples in the mix are negative or at least one is positive. Mixing reduces the number of tests he needs.

Each sample has enough saliva, so he can test the same sample as many times as he wants. The tests are perfectly accurate, so different tests never give different results for the same sample.

Adam wants to use as few tests as possible. He is busy with testing, so you are responsible for optimizing the process.

Local statistics show that any given sample is positive with probability $P$. Whether one sample is positive does not affect any other sample. Use this information to decide which tests to perform.

The judge for this problem is not adaptive. The positivity of each sample is fixed before the program runs. Whether each sample is positive is decided independently with probability $P$ by a fair random number generator.