Faster than exp(((64/9)^1/3 + o(1))*((log n)^1/3 (log log n)^2/3)). The time building the table is not counted as that happens ahead of time.

The idea is to do it once. A lot can likely be compressed, while keeping access time log-linear. Store it passively, so that it won't need power except for reading, like mask ROM or CD-ROM do not.