Cho số nguyên dương n, người ta tạo ra số nguyên m bằng cách viết liên tiếp nhau các số nguyên từ 1 đến n. Ví dụ, với n = 13, ta có m = 12345678910111213.

Người ta tiến hành thu gọn m  bằng cách: Trong số m  lần lượt xoá tất cả các chữ số ở vị trí chẵn thu được số m1, sau đó trong m1 ta lại xoá tất cả các chữ số ở vị trí lẻ thu được số m2, rồi lại xoá tất cả các chữ số ở vị trí chẵn trong m2, . . . cho đến khi chỉ còn lại một chữ số.

      m =12345678910111213 " =135790123 " =3702 " =30 " =0

Yêu cầu: Cho số nguyên dương n (1 < n ≤ 106). Hãy xác định chữ số còn lại sau quá trình thu gọn số m tương ứng.

Input

Dữ liệu vào gồm nhiều bộ dữ liệu tương ứng với nhiều test. Dòng đầu tiên chứa số nguyên K (K≤10), là số bộ dữ liệu.

Tiếp theo là K dòng, mỗi dòng tương ứng với một bộ dữ liệu chứa một số nguyên dương n.

Output

Với mỗi bộ dữ liệu, ghi ra trên một dòng câu trả lời, ghi một số nguyên là chữ số còn lại sau quá trình thu gọn số m.