Một số nguyên dương được gọi là palindrome nếu cách biểu diễn của nó trong hệ thập phân giống nhau khi đọc từ trái sang phải và từ phải sang trái. Cho một số nguyên dương \(K\) không quá \(10^6\) chữ số, hãy tìm số palindrome nhỏ nhất mà lớn hơn \(K\). Các số không có số \(0\) ở vị trí đầu.

Input

• Dòng đầu tiên là số lượng bộ test \(t\)
• \(t\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(k\)

Output

• Mỗi dòng là Số palindrome tìm được tương ứng với từng bộ test

Constraints

• \(1 <= K <= 10^6\)

Example

Sample input 1

2
808
2133

Sample output 1

818
2222