Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT015H - ACM PTIT 2015 H - Thu gọn

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.

Example

Input:
1
3 Output: 3

Được gửi lên bởi:adm
Ngày:2015-04-19
Thời gian chạy:3s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP CPP C++ 4.3.2 CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2022-06-26 17:28:56
Bài này có thể dùng toán học để làm nhanh hơn (n=10^17~0.01s) còn không thì chạy trâu vẫn AC bài này :v (Ngồi nghiên cứu toán số mãi mới ra công thức)
2017-07-11 18:19:24
bài khó v mà s nhiều ng làm dc v @@
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.