수 뒤집어 세기 (작은 입력)

수 세기 낭송회에서 공연자는 마이크를 잡고 수 $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^6$

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

$N$이 19일 때는 뒤집기가 도움이 되지 않아서 1부터 19까지 그대로 세는 것이 최선이다.

$N$이 23일 때는 12까지 센 다음 뒤집어 21로 가고, 거기서 23까지 세는 것이 최선이다. 이때 말하는 수는 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22, 23이다.