Solution:

The answer is (A). Since, for nonnegative numbers, $\sqrt{a}<b$ if and only if $a<b^{2}$, the question asks after how many squarings $\left(\cdots\left(2^{2}\right)^{\cdots \cdots}\right)^{2}=2^{2^{n}}$ the result exceeds $123.456.789$. Since $2^{10}=1024>10^{3}$, one finds that $2^{2^{5}}=2^{32}>10^{9}=1.000.000.000>123.456.789$. It is also observed that 4 square root extractions are not enough, since $2^{16}=65536$.