Cho một số nguyên dương \(N\).

Một số nguyên \(K\) khác được định nghĩa như sau:

(\(K_i\) là chữ số thứ \(i\) của số nguyên dương \(K\), \(N_j\) là chữ số thứ \(j\) của số nguyên dương \(N\))

\(K_1 = N_1\)

\(K_2 = LD (N_1 + N_2)\)

\(K_3 = LD (N_1 + N_2 + N_3)\)

…

Trong đó, hàm \(LD (n)\) được định nghĩa là chữ số cuối cùng của số nguyên \(n\).

Ví dụ \(LD (15) = 5\).

Yêu cầu: cho số \(N\). viết ra số \(K\).

Input

• Dòng đầu ghi \(Q (Q \le 100)\) – số câu hỏi.
• \(Q\) dòng tiếp theo, mỗi dòng ghi ra số nguyên dương \(N (N \le 10^{18})\).

Output

• Ứng với mỗi câu hỏi, in ra kết quả cần tìm.

Example

3
108
254623
3747472777455532

119
271792
3041524185949479