Số đẹp
Xem PDF
Nộp bài
Điểm:
1800 (thành phần)
Thời gian:
0.3s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Tác giả:
Dạng bài
Số đẹp là số có tổng bình phương các chữ số của nó (trong dạng biểu diễn thập phân) là một số nguyên tố. Ví dụ: 23 là một số đẹp vì 2^2+3^2=13 là một số nguyên tố.
Dãy các số đẹp lần lượt là: 11,12,14,16,21,23,25,27,32,38,\dots. Các số đẹp được đánh số thứ tự tăng dần theo giá trị bắt đầu số thứ nhất là 11, số thứ hai là 12, ..., số thứ mười là 38
Yêu cầu: Cho số nguyên dương N. Hãy tìm số đẹp thứ N
Input, Output và Subtasks
Input
- Dòng thứ nhất gồm số t chỉ số testcase (1\le t\le 10^5)
- t dòng tiếp theo, mỗi dòng gồm duy nhất một số n (1\le n\le 10^{18})
Output
- Xuất ra t dòng, dòng thứ i xuất ra kết quả tương ứng của dòng thứ i
Subtasks
- Subtask 1 (20\%): n\le 100.
- Subtask 2 (20\%): n\le 10^4.
- Subtask 3 (20\%): n\le 10^6.
- Subtask 4 (20\%): t\le 100.
- Subtask 5 (10\%): t\le 10^4.
- Subtask 6 (10\%): Không có giới hạn gì thêm.
Sample
Input
10
1
2
3
4
5
6
7
8
9
10
Output
11
12
14
16
21
23
25
27
32
38
Bình luận