Comment by alasdair_

It can fit in a single bit if your algorithm is optimized for "primes that are equal to M49" :)