Say you want to compute ${19}^{100}.$ Using the naive method, one needs to do exactly $99$ multiplications. Your task is to find out how to find out exactly how many multiplications do we need if we use the recursive exponentiation algorithm that we did in the class.

$8$

$10$

$9$

$7$