Broken Calculator

Chanwoo, shaken after yet another stream of Wrong Answer verdicts, accidentally swung a shotgun at his beloved calculator. Most of the buttons broke from the impact. The only buttons still working add $4$ to the number on the screen, subtract $4$, multiply by $4$, or divide by $4$. The decimal point function also broke, so a number that is not divisible by $4$ cannot be divided by $4$. Fortunately, the screen still displays negative numbers correctly.

Unwilling to give up the calculator, Chanwoo decided to keep using it. He wondered about the fewest button clicks needed to show a given integer on the screen. Given $N$, find the minimum number of button clicks needed to display $N$. The screen starts at $0$.

The first line contains the number of test cases $T$. ($1\leq T \leq 10\ 000$)

Each test case gives an integer $N$ to produce. ($0\leq N \leq 10^{18}$)

For each test case, print the minimum number of button clicks needed to produce $N$.