고장난 계산기

오늘도 무수한 Wrong Answer를 받고 멘탈이 나간 찬우는 실수로 애지중지하던 계산기에 샷건을 내려치고 말았다! 대부분의 버튼이 충격으로 고장났고, 무사히 작동하는 버튼은 계산기의 화면에 출력된 수에 $4$를 더하는 버튼, $4$를 빼는 버튼, $4$를 곱하는 버튼, $4$를 나누는 버튼 뿐이었다. 또, 계산기의 소수점 기능이 망가져서 $4$로 나눠떨어지지 않는 수를 $4$로 나눌 수 없게 되었다. 다행히 계산기 화면에서 음수를 출력하는 기능은 정상적으로 동작했다.

이대로 계산기를 잃을 수 없었던 찬우는 어떻게든 계산기를 사용하기로 했고, 문득 화면에 원하는 정수를 띄우기 위한 최소한의 버튼 클릭 횟수가 얼마인지 궁금해졌다. 입력으로 $N$이 주어질 때, $N$을 화면에 띄우기 위해 필요한 최소한의 버튼 클릭 횟수를 구하여라. 초기 화면에 적힌 정수는 $0$이다.

첫 번째 줄에 테스트케이스의 수 $T$가 주어진다. ($1\leq T \leq 10\ 000$)

각 테스트케이스에 대해, 만들어야 할 정수 $N$이 주어진다. ($0\leq N \leq 10^{18}$)

각 테스트케이스에 대해 $N$을 만들기 위해 필요한 최소한의 버튼 클릭 횟수를 출력한다.