Trường THPT Chuyên Hoàng Văn Thụ - Hòa Bình

Bờm rất thích những tính chất thú vị của các dãy số. Bố cậu biết vậy nên đã đố cậu giải được bài toán sau:

Cho 1 dãy số

Đặt X= (a_n+1 – a_n)². Hỏi rằng chữ số cuối cùng của số X là số nào?

Bờm đang cố gắng suy nghĩ để tìm ra cách giải. Bạn là một lập trình viên giỏi nên bạn hãy giúp cậu ấy giải bài toán trên.

Input

• Dòng đầu ghi số K (K thuộc tâp Z, 1 ≤ K ≤ 1000).
• K dòng tiếp theo, mỗi dòng có 1 giá trị duy nhất là số nguyên dương n (với n≤10¹⁵).

Output

• Gồm k dòng, mỗi dòng ghi một chữ số duy nhất tìm được ứng với dòng có giá trị n trong file dữ liệu vào.

Example

Input:
2
1
4
Output:
4

5

* Chú ý: 60% số test có n ≤10000.