Counting only $\{+,-,*,/,\%,>,<,==,<=,>=\},$ determine the exact number of basic operations that would be performed when the following function foo is invoked on the given value of n$.$

def foo$($n$)$:

if n $==0$:

return $1$

elif n $\%2==0$:

v $=$ foo$($n$/2)$

t $=0$

for i in range$($n$)$:

t $=$ t $+$ v

return t

else:

v $=$ foo$($n$-1)$

return v $+1$

Input Format

A line containing the integer t

Each of the next t lines contains a single integer ni

Constraints

$1<=$ t $<=100$

$1<=$ n $<=10^9$

Output Format

t lines, each of which is a single integer indicating the number of basic operations that would have been executed by foo on the corresponding value of n read from the input.

Sample Input $0$

$2$

$2$

$3$

Sample Output $0$

$12$

$17$

Explanation $0$

In the first test n$=2$ and when we invoke foo on $2,$ it checks if $2==0$ incurring $1$ operation, then it goes on to check whether $2\%2==0$ which incurs $2$ more operations $($for a total of $3).$ Since the condition is true, the consequent expressions must now be performed. The recursive call invokes one $/($so now our runnig total is $4,$ so far$).$

In the recursive call, n$=1,$ so once again, it checks the predicates of the if and elif conditional statements, which costs $3$ operations in total $($now the total is $4+3=7)$ and since both are false, executes the alternative clause $($introduced by else$).$ That code fragment invokes the $-$ operation $($for a total of $8$ now$)$ then a recursive call. On the recursive call, $($n$=0),$ only $1$ basic operation $(==)$ is performed, bringing the total to $9.$ Finally an invocation of the $+$ operation brings the total to $10.$

When the code returns to the previous invocation $($n$=2),$ the value of v has been determined, and the code can resume to perform a for loop for n$=2$ iterations. This causes two more invocations of $+,$ taking the total to $10+2=12.$

For the n$=3$ case, the condition that gets executed is the else clause, by which time $3$ basic operations have already been performed $($two $==$ and one $\%).$ The recursive call to n$=2$ incurs $12$ operations $($as we just learned$),$ and the $-$ and $+$ operations add $2$ more. So that makes it a total of $3+1+12+1=17$ operations.

#$!/$bin$/$python$3$

import os

import sys

# Complete the function below.

def countFooOps$($n$)$:

# Write your code here.

if $\_\_$name$\_\_==\text{'}\_\_$main$\_\_\text{'}$:

f $=$ open$($os$.$environ$[\text{'}$OUTPUT$\_$PATH'$],\text{'}$w$\text{'})$

t $=$ int$($input$())$

for t$\_$i in range$($t$)$:

n $=$ int$($input$())$

result $=$ countFooOps$($n$)$

f$.$write$($str$($result$)+"$

$")$

f$.$close$()$