SVMC STP Class 0626

Problem

Tèo và Tí là đôi bạn thân, họ thường đố nhau về những bài học đã được học trên trường. Cách làm này làm 2 bạn rất dễ áp dụng kiến thức đã học và nhanh hiểu bài.

Một hôm, Tí qua nhà Tèo chơi và đố Tèo về một phép toán nén số nguyên.

Nghe qua thì rất đơn giản, Tí định nghĩa phép nén một số nguyên dương là tính tổng các chữ số của nó.

Sao cho, sau một số phép nén, thì số còn lại chỉ có một chữ số và không nén được nữa.

Ví dụ cho số 86. Sau phép nén thứ nhất ta đk: 8+6=14. Sau phép nén thứ 2: 1+4=5 => Số nén tối giản của 86 là 5.

Cho một số nguyên hãy tìm số nén tối giản của nó.

Tí rất hứng thú với phép toán này, và cậu quyết định lập trình để giải quyết bài toán thay vì tính tay. Các bạn hãy cùng Tí giải quyết bài toán này nhé.

Input

Dòng đầu chứa số bộ test (1 <= T <= 100).

T dòng tiếp theo, mỗi dòng tiếp theo chứa 1 số nguyên dương N. (N <= 10^9)

Output

Kết quả mỗi testcase được in trên 1 dòng. Với:

Bắt đầu bằng ký tự "#", tiếp theo là số thứ tự của testcase đó, tiếp đến là 1 khoảng trắng (dấu cách), và cuối cùng là kết quả của số nén tối giản tương ứng.

Example

Input:
3
43
111
57871
Output:
#1 7
#2 3
#3 1