Cho số nguyên không âm \(n\), cần tìm số \(m\) nhỏ nhất thỏa mãn điều kiện:

• Số \(m\) lớn hơn hoặc bằng \(n\).
• Tổng các chữ số của \(m\) nhỏ hơn tổng các chữ số của \(n\).

Input

• Dòng đầu chứa số nguyên dương \(t\) là số bộ dữ liệu.
• Dòng thứ \(i\) (\(1 \le i \le t\)) chứa một số nguyên không âm \(n\).

Output

• Mỗi dòng là số \(m\) tương ứng tìm được, nếu không tồn tại số \(m\) đưa ra -1.

Scoring

• Subtask \(1\) (\(60\%\) số điểm): \(n \le 10^6, t \le 3\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 10^6, t \le 3 \times 10^4\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 10^{16}, t \le 3 \times 10^4\).

Example

2
5
59

10
60