Nhập vào 1 số nguyên ~n~, thực hiện thay thế các chữ số 0 trong biểu diễn thập phân của ~n~ thành các chữ số 5 và in ra kết quả.

Input

Dòng đầu tiên chứa số nguyên ~T~ (~1 \leq T \leq 10^5~) - cho biết số bộ dữ liệu cần kiểm tra.

~T~ dòng tiếp theo, mỗi dòng chứa 1 số nguyên ~n~ (~0 \leq n \leq 10^{12}~).

Output

Ứng với mỗi bộ dữ liệu đầu vào, in ra số ~n~ theo yêu cầu của đề bài.

Sample Test

Input

2
1005
1234

Output

1555
1234