Liệt kê một dãy số tự nhiên liên tiếp từ 1 đến \(N\). Thực hiện hai lần xóa số:

• Lần 1: Xóa tất cả các số chia hết cho \(2\) đi
• Lần 2: Xóa tất cả các số chia hết cho \(3\) đi

Yêu cầu: Sau khi dãy số đã xóa thì dãy số còn bao nhiêu số chưa bị xóa?

Ví dụ: \(N = 11\), đáp án là \(4\). Vì những số chưa bị xóa là \(1, 5, 7, 11\)

\({\color{Red} 1}\ 2\ 3\ 4\ {\color{Red} 5}\ 6\ {\color{Red} 7}\ 8\ 9\ 10\ {\color{Red} {11}}\)

Dữ liệu

• Một dòng chưa số nguyên dương \(N\ (N \le 10^9)\)

Kết quả

• Số lượng số chưa bị xóa

Ví dụ

Dữ liệu

24

Kết quả

8

Nguồn: Đề thi thử tỉnh Nghệ An 2021

Cho một dãy số có dạng như sau \(1, 2, 5, 10, 17, 26…\) Nhập vào 2 số \(A\) và \(B\), tính tổng của số hạng thứ \(A\) và số hạng thứ \(B\) trong dãy trên.

Ví dụ: \(A=3\) và \(B=5\) thì kết quả là \(22\). Vì số hạng thứ \(3\) là \(5\), số hạng thứ \(5\) là \(17\) vậy tổng là \(22\).

Dữ liệu

• Dòng thứ nhất chứa số \(A\)
• Dòng thứ nhất chứa số \(B\)

Ràng buộc: \(1 \le A \le B \le 2\times 10^7\)

Kết quả

• Kết quả của bài toán

Ví dụ

Dữ liệu

3
5

Kết quả

22

Nguồn: Đề thi thử tỉnh Nghệ An 2021

Cho số \(N\) là số trang sách của quyển sách. Hãy đếm số lượng chữ số cần dùng để đánh số thứ tự cho các trang sách này.

Ví dụ: \(N=11\) thì đưa ra kết quả là \(13\). Vì đánh số trang \(1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11\) thì dùng hết \(13\) chữ số.

Dữ liệu

• Dòng duy nhất chứa số nguyên \(N\)

Ràng buộc: \(N \le 7\times 10^7\)

Kết quả

• Số lượng chữ số để đánh số thứ tự các trang sách

Ví dụ

Dữ liệu

24

Kết quả

39

Nguồn: Đề thi thử tỉnh Nghệ An 2021

Hình vuông bậc \(N\) là hình vuông được tạo bởi \(N \times N\) hình vuông đơn vị, mỗi hàng hay mỗi cột của hình vuồng đều có \(N\) hình vuông đơn vị như hình dưới đây.

Yêu cầu: Cho số tự nhiên \(N\). Đếm số hình vuông có trong hình vuông bậc \(N\).
Ví dụ: \(N=2\), thì đưa ra kết quả là 5.

Dữ liệu

• Một số nguyên \(N\) là hình vuông bậc \(N\)

Ràng buộc: \(N \le 10^5\)

Kết quả

• In ra kết quả là số lượng hình vuông có trong hình vuông bậc \(N\).

Ví dụ

Dữ liệu

4

Kết quả

30

Nguồn: Đề thi thử tỉnh Nghệ An 2021

Cho một xâu dài vô hạn chứa tất cả các số nguyên dương theo trình tự tăng dần:

\(12345678910111213141516171819202122232425 \ldots\)

Nhiệm vụ của bạn là xử lí \(q\) truy vấn trả lời cho câu hỏi: số nào nằm ở vị trí thứ \(k\) trong xâu?

Input

• Dòng đầu tiên chứa một số nguyên duy nhất \(q\): số lượng truy vấn.
• Sau đó gồm \(q\) dòng tiếp theo biểu diễn các truy vấn, mỗi dòng là một số nguyên \(k\): vị trí của kí tự cần tìm trong xâu (xâu được đánh số từ \(1\)).

Output

• Với mỗi truy vấn, in ra kết quả tương ứng trên từng dòng.

Constraints

• \(1 \le q \le 1000\)
• \(1 \le k \le 10^{18}\)

Example

Sample input

3
7
19
12

7
4
1