카운터 컬처

카운팅 포에트리 슬램에서 공연자는 마이크를 잡고 수 N을 선택한 뒤, 1부터 N까지 소리 내어 센다. 즉, 먼저 1을 말하고, 그다음에는 직전에 말한 수보다 1만큼 큰 수를 반복해서 말하며, N을 말한 뒤 멈춘다.

이제 당신이 공연할 차례이지만, 이 과정이 지루하다고 생각하여 속도를 높일 변화를 주고 싶다. 때로는 직전 수에 1을 더하는 대신 그 수의 자릿수를 뒤집을 수 있다(이로 인해 생기는 선행 영은 제거한다). 예를 들어, "16"을 말한 다음에는 "17" 또는 "61"을 말할 수 있고, "2300"을 말한 다음에는 "2301" 또는 "32"을 말할 수 있다. 한 번의 공연에서 원하는 만큼 여러 번 뒤집을 수 있으며, 전혀 뒤집지 않아도 된다.

처음 말하는 수는 반드시 1이어야 한다. 수 N에 도달하기 위해 말해야 하는 수의 최소 개수는 얼마인가? 1과 N도 이 합계에 포함된다. 같은 수를 여러 번 말하면, 말한 각 횟수를 별도로 센다.

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 100.

작은 데이터 세트

시간 제한: 240초. 1 ≤ N ≤ $10^{6}$.

큰 데이터 세트

시간 제한: 480초. 1 ≤ N ≤ $10^{14}$.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어진다. 각 줄에는 도달해야 하는 수인 정수 N 하나가 주어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이고(1부터 시작한다), y는 말해야 하는 수의 최소 개수이다.

케이스 #2에서는 뒤집기가 도움이 되지 않으므로, 단순히 19까지 세는 것이 최적의 전략이다.

케이스 #3에서 최적의 전략은 12까지 센 뒤 21로 뒤집고, 이어서 23까지 계속 세는 것이다. 즉, 말하게 되는 수는 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22, 23이다.