It depends on the kind of traveler (business travelers have shorter lead-time, leisure travelers have longer), but 3 weeks is a reasonable guess—probably on the shorter end—for what Google customers will be looking for.