신비한 의식

크라토스가 신비한 의식이 적힌 책을 찾았다. 처음에 $n$으로 임의의 수를 고를 수 있다. $n$에 대해 다음 동작을 수행한다.

• $n$을 10진수로 표기했을 때 가장 낮은 자리의 숫자를 기억한다.
• $n$이 10으로 나누어떨어질 때까지 기억해 둔 숫자를 $n$에 더한다.
• $n$을 10으로 나누고 의식의 처음으로 돌아간다.

의식은 무한히 계속된다. 책에 따르면 의식 과정에서 $n$이 가지는 가장 작은 값이 그 수의 마법의 수이다. 크라토스는 아직 시작할 $n$을 정하지 못했다. 시작 값마다 그에 해당하는 마법의 수를 구하는 것을 도와 달라.

첫 줄에 테스트 케이스의 개수 $t$가 주어진다 ($1 \le t \le 100000$). 다음 $t$개의 줄에는 테스트가 하나씩 주어진다. 각 테스트는 정수 $n_i$ 하나이며, $i$번째 테스트에서 $n$의 초기 값이다 ($1 \le n_i < 10^{500001}$). 모든 테스트의 수 길이 합은 500000을 넘지 않는다.

각 테스트마다 한 줄에 의식 과정에서 $n$이 가질 수 있는 가장 작은 값을 출력한다.