Just be aware that there are more prime hashes than there are hashes with a specific 2 hex-digit prefix, so even relatively short messages will be much harder to find.