고장난 계산기

오늘도 무수한 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$을 만들기 위해 필요한 최소 버튼 클릭 횟수를 출력한다.