Hãy lập trình nhập vào 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ả. Ví dụ: Với ~n=1005~ thì sau khi thực hiện thay thế ta thu được số ~1555~. Còn với ~n=1234~, thì không có chữ số nào bị thay thế và kết quả vẫn là số ~1234~.

Input

Dòng đầu tiên của đầu vào chứa số nguyên ~T~ cho biết số bộ dữ liệu cần kiểm tra. Mỗi bộ dữ liệu gồm một dòng chứa một số nguyên ~n~.

Output

Ứng với mỗi bộ dữ liệu đầu vào, chương trình của bạn cần in ra số ~n~ sau khi thay thế các chữ số của ~n~ theo yêu cầu đề bài.

Constraints

• ~1 \leq T \leq 10^5 ; 0 \leq n \leq 10^{12}~.

Sample Input

2
1000
1234

Sample Output

1555
1234

Bạn được tặng một con xúc xắc hình khối lập phương với ~6~ mặt. Mỗi mặt của con xúc xắc có in một số chấm, số lượng chấm trong phạm vi từ ~1~ đến ~6~, giống như bất kỳ con xúc xắc thông thường nào. Bạn được biết số chấm trên một mặt của xúc xắc, nhiệm vụ của bạn là đoán số ở mặt đối diện của xúc xắc.

Dữ liệu:

• Dòng đầu tiên của đầu vào chứa số nguyên ~T~ cho biết số bộ dữ liệu cần kiểm tra. Mỗi bộ dữ liệu gồm một dòng chứa một số nguyên ~n~ cho biết số chấm trên một mặt của con xúc xắc.

Kết quả:

• Ứng với mỗi bộ dữ liệu đầu vào, chương trình của bạn cần in ra số ~n~ sau khi thay thế các chữ số của ~n~ theo yêu cầu đề bài.

Ràng buộc:

• ~1 \leq T \leq 500 ; 1 \leq n \leq 6~.

Ví dụ:

Input

2
6
2

Output

1
5

Có ~N~ bệnh nhân đến khám tại phòng khám. Giả sử rằng cứ sau ~X~ (phút) thì có một bệnh nhân mới đến phòng khám. Ngoài ra, bác sĩ sẽ chỉ dành ~10~ phút để khám cho mỗi bệnh nhân. Nhiệm vụ của bạn là tính toán thời gian (bằng phút) mà bệnh nhân cuối cùng cần phải chờ đến lượt mình được bác sĩ khám bệnh.

Input

Dòng đầu tiên của đầu vào chứa số nguyên ~T~ cho biết số bộ dữ liệu cần kiểm tra. Mỗi bộ dữ liệu gồm một dòng chứa hai số nguyên ~N~ và ~X~.

Output

Ứng với mỗi bộ dữ liệu đầu vào, chương trình của bạn cần in ra một dòng chứa số ~M~ là số phút mà bệnh nhân cuối cùng cần chờ bác sĩ tại phòng khám.

Constraints

• ~1 \le T \le 500; 1 \le N \le 100; 0 \le X \le 30~.

Sample Input

5
4 5
5 3
6 5
7 6
8 2

Sample Input

15
28
25
24
56

Cho số nguyên không dấu ~N~. Hãy kiểm tra tính chẵn lẻ của ~N~. Trong bài toán này tính chẵn lẻ của ~N~ là số bit ~1~ trong biểu diễn nhị phân của ~N~. Nghĩa là nếu trong biểu diễn nhị phân của ~N~ có chứa một số chẵn các bit ~1~ thì ~N~ được coi là có tính chẵn, và ngược lại thì ~N~ có tính lẻ. Ví dụ: ~N=13_{10}=1101_2~ nên ~N~ có tính lẻ, còn ~N=9_{10}=1001_2~ nên có tính chẵn.

Dữ liệu:

• Dòng đầu tiên của đầu vào chứa số nguyên ~T~ cho biết số bộ dữ liệu cần kiểm tra. Mỗi bộ dữ liệu gồm một dòng chứa số nguyên ~N~.

Kết quả:

• Ứng với mỗi bộ dữ liệu đầu vào, chương trình của bạn cần in ra một dòng chứa thông báo "odd" nếu ~N~ có tính lẻ và "even" nếu ~N~ có tính chẵn.

Ràng buộc

• ~1 \leq T \leq 500 ; 0 \leq N \leq 10^{12}~.

Ví dụ:

Input

2
13
9

Input

odd
even

Dữ liệu:

• Dòng đầu tiên của đầu vào chứa số nguyên ~T~ cho biết số bộ dữ liệu cần kiểm tra. Mỗi bộ dữ liệu gồm một dòng chứa số nguyên ~N~.

Kết quả:

• Ứng với mỗi bộ dữ liệu đầu vào, chương trình của bạn cần in ra một dòng chứa số lượng tin nhắn cần gửi để ~N~ học sinh đều nhận được tất cả ~N~ câu chuyện hài.

Ràng buộc:

• ~1 \leq T \leq 100 ; 1 \leq N \leq 10^5~.

Ví dụ:

Input

1 
2

Output

2

Một số được gọi là "số tam giác" nếu ta có thể biểu diễn nó dưới dạng lưới hình tam giác gồm các điểm sao cho các điểm tạo thành một tam giác đều, tức là hàng đầu tiên có một điểm, hàng thứ hai có hai điểm, hàng thứ ba có ba điểm.... Các số tam giác bắt đầu là ~1,3(=1+2), 6(=1+2+3)~, ~10(=1+2+3+4)~, xem hình minh họa sau:

Yêu cầu: Cho biết số nguyên dương ~N~, hãy cho biết ~N~ có phải số tam giác hay không?

Dữ liệu:

• Dòng đầu tiên của đầu vào chứa số nguyên ~T~ cho biết số bộ dữ liệu cần kiểm tra. Mỗi bộ dữ liệu gồm một dòng chứa số nguyên ~N~ duy nhất.

Kết quả:

• Ứng với mỗi bộ dữ liệu đầu vào, chương trình của bạn cần in ra một dòng chứa số ~1~ nếu ~N~ là số tam giác, ngược lại thì in ra số ~0~ .

Ràng buộc:

• ~1 \leq T \leq 100 ; 1 \leq N \leq 10^7~.

Ví dụ:

Input

5
3
4
6
55
345

Output

1
0
1
1
0