짝수 숫자

Supervin에게는 독특한 계산기가 있다. 이 계산기에는 화면과 더하기 버튼, 빼기 버튼만 있다. 현재 계산기 화면에는 정수 N이 표시되어 있다.

더하기 버튼을 누르면 현재 계산기 화면에 표시된 수가 1만큼 증가한다. 마찬가지로 빼기 버튼을 누르면 현재 계산기 화면에 표시된 수가 1만큼 감소한다. 계산기는 앞에 붙는 0을 표시하지 않는다. 예를 들어 계산기 화면에 100이 표시되어 있을 때 빼기 버튼을 한 번 누르면 계산기에 99이 표시된다.

Supervin은 홀수 숫자를 "이상하다"고 생각하기 때문에 좋아하지 않는다. 따라서 그는 계산기 버튼만 사용하여 십진수 표기에 짝수 숫자만 포함된 정수를 표시하려 한다. 계산기가 조금 낡아 버튼을 누르기 어렵기 때문에, 버튼을 누르는 횟수를 최소화하려 한다.

Supervin이 계산기에 홀수 숫자가 없는 정수를 표시하기 위해 눌러야 하는 버튼의 최소 횟수를 구하도록 도와주자.

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ N ≤ $10^{5}$.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ N ≤ $10^{16}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 처음에 Supervin의 계산기에 표시된 정수 N을 포함하는 한 줄로 시작한다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작), y은 위에서 설명한 버튼을 누르는 최소 횟수이다.

예제 케이스 #1에서는 계산기에 처음 표시된 정수에 홀수 숫자가 없으므로 버튼을 누를 필요가 없다.

예제 케이스 #2에서는 빼기 버튼을 세 번 누르면 계산기에 8이 표시된다. 버튼을 세 번보다 적게 눌러 요구 사항을 만족할 방법은 없다.

예제 케이스 #3에서는 빼기 버튼을 한 번 누르거나(그러면 계산기에 0이 표시된다) 더하기 버튼을 한 번 누르면 계산기에 홀수 숫자가 없는 정수가 표시된다.

예제 케이스 #4에서는 더하기 버튼을 두 번 누르면 계산기에 2020이 표시된다. 버튼을 두 번보다 적게 눌러 요구 사항을 만족할 방법은 없다.