숫자 세기 공연 (큰 입력)

숫자 세기 공연에서는 공연자가 마이크를 잡고 수 $N$을 하나 고른 뒤 1부터 $N$까지 소리 내어 센다. 먼저 1을 말하고, 그 뒤로는 직전에 말한 수보다 1 큰 수를 계속 말하다가 $N$을 말하면 멈춘다.

이제 당신 차례인데, 이 과정이 지루해서 규칙을 하나 더 쓰기로 했다. 직전 수에 1을 더하는 대신, 직전 수의 자릿수를 뒤집어서 말해도 된다. 뒤집은 결과의 앞에 오는 0은 버린다. 예를 들어 "16"을 말한 다음에는 "17"이나 "61"을 말할 수 있고, "2300"을 말한 다음에는 "2301"이나 "32"를 말할 수 있다. 한 공연에서 뒤집기는 원하는 만큼 써도 되고, 한 번도 쓰지 않아도 된다.

처음 말하는 수는 반드시 1이다. $N$에 도달하려면 수를 최소 몇 개 말해야 하는지 구하라. 1과 $N$도 이 개수에 포함한다. 같은 수를 여러 번 말하면 말한 횟수만큼 따로 센다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에 도달해야 하는 수 $N$이 한 줄에 하나씩 주어진다.

제한

• $1 \le T \le 100$
• $1 \le N \le 10^{14}$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 말해야 하는 수의 최소 개수이다.

예제의 두 번째 테스트 케이스에서는 뒤집기가 도움이 되지 않아 19까지 그대로 세는 것이 최적이다.

세 번째 테스트 케이스에서는 12까지 센 다음 뒤집어 21로 가고, 다시 23까지 세는 것이 최적이다. 이때 말하는 수는 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22, 23이다.