On the minimal power of $q$ in a Kazhdan-Lusztig polynomial

For $w$ in the symmetric group, we provide an exact formula for the smallest positive power $q^{h(w)}$ appearing in the Kazhdan-Lusztig polynomial $P_{e,w}(q)$. We also provide a tight upper bound on $h(w)$ in simply-laced types, resolving a conjecture of Billey-Postnikov from 2002.