Số học lẩu thập cẩm

Bảo Anh là em họ của Anh Kha, và cậu rất thích những điều siêu to khổng lồ. Sau khi đạt được một số điểm siêu to khổng lồ trong kì thi chọn Học Sinh Giỏi của hành tinh Trái Nước, Bảo Anh được đại ca ami tặng một dãy số siêu to khổng lồ.

Dãy số được cho gồm \(N\) phần tử \(a_1, a_2, \dots, a_n\). Cảm thấy vẫn chưa xứng đáng với thành tích của mình, Bảo Anh muốn ami tặng thêm một số \(X\) siêu to nữa.

Vẫn chưa cảm thấy đủ, Bảo Anh quyết định tìm một số \(Y \geq X\) nhỏ nhất mà \(Y\) chia hết cho một số bất kì trong dãy \(a\) vì cậu nghĩ số này là một số siêu to khổng lồ.

Input

• Dòng đầu tiên chứa hai số \(N, X\)
• Dòng thứ hai chứa dãy \(a\), gồm \(N\) số nguyên dương \(a_1, a_2, \dots, a_n\)

Output

• In ra một số nguyên duy nhất là đáp án bài toán

Constraints

• \(1 \leq n \leq 10^5\)
• \(0 \leq x \leq 10^{18}\)
• \(1 \leq a_i \leq 10^{18}\)

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \leq 100, a_i \leq 10^4, x \leq 2*10^4\)
• Subtask \(2\) (\(20\%\) số điểm): \(a_i \leq 10^6, x \leq 2*10^6\)
• Subtask \(3\) (\(30\%\) số điểm): Không có điều kiện gì thêm

3 5
2 3 4

6

Cho số nguyên dương \(a\). Hãy đếm xem có bao nhiêu số tự nhiên \(b < a\) mà \(a^3 - b^3\) là số nguyên tố.

Input

• Dòng đầu tiên chứa một số nguyên dương \(q \ (q \leq 100)\), số lượng truy vấn cần trả lời.
• \(q\) dòng tiếp theo, mỗi dòng chứa một số nguyên dương \(a\).

Output

• In ra \(q\) dòng, mỗi dòng là đáp án cho một truy vấn

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(a \leq 200\)
• Subtask \(2\) (\(30\%\) số điểm): \(a \leq 2000\)
• Subtask \(3\) (\(40\%\) số điểm): \(a \leq 10^6\)

Example

3
1
2
3

0
1
1

Cho số nguyên dương \(n\). Gọi \(s\) là số nguyên dương nhỏ nhất có chính xác \(n\) ước (ở đây ta chỉ tính ước dương).

Yêu cầu: Cho số nguyên dương \(n\). In ra \(s\) (Biết rằng: Đề ra đảm bảo \(s\le 10^{18}\))

Input

• Một dòng duy nhất chứa số nguyên \(n(1\le n\le 1000)\)

Output

• In ra \(s\) cần tìm

Example

2

2

Trong số học, số phong phú là các số mà tổng các ước số của số đó (không kể chính nó) lớn hơn số đó. Ví dụ, số \(12\) có tổng các ước số (không kể \(12\)) là \(1 + 2 + 3 + 4 + 6 = 16 > 12\). Do đó \(12\) là một số phong phú.

Bạn hãy lập trình đếm xem có bao nhiêu số phong phú trong đoạn [\(L,R\)].

Input

• Gồm 2 số \(L, R\) (\(1 \leq L \leq R \leq 10^6\))

Output

• Gồm 1 số nguyên duy nhất là số số phong phú trong đoạn [\(L, R\)].

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(1 \leq L \leq R \leq 10^3\)
• Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm

Example

1
50

9

Ký hiệu \(D(n)\) là số lượng ước số của số tự nhiên \(n\), ví dụ: \(D(10)=4\) và \(D(12)=6\). Với \(L\) và \(R\) cho trước \((L\leq R)\), hãy tính tổng \(D(L)+D(L+1)+...+D(R-1)+D(R)\).

Input

• Dòng đầu chứa số nguyên dương \(T\leq 10^6\) là số lượng câu hỏi.

• \(T\) dòng sau, mỗi dòng chứa hai số nguyên dương \(L\) và \(R\) thể hiện một câu hỏi \(\left(1\leq L\leq R\leq 10^6\right)\).

Output

• Gồm \(T\) dòng, mỗi dòng chứa một số nguyên dương là câu trả lời cho câu hỏi tương ứng.

Example

2
1 12
4 5

35
5

Mọi số nguyên dương \(a\) đều có thể viết được dưới dạng lũy thừa bậc \(n\) của số nguyên dương \(b\) (với \(n\) là số tự nhiên). Chẳng hạn: \(27 = 3^3\); \(8 = 8^1\). Một số nguyên dương \(a\) có thể có nhiều cách biểu diễn dưới dạng một lũy thừa, chẳng hạn: \(81 = 81^1 = 9^2 = 3^4\).
Yêu cầu: Cho trước 3 số nguyên dương \(a; b; c\). Gọi \(x\) là tích của 3 số \(a; b; c\). Hỏi trong các cách viết số \(x\) thành một lũy thừa bậc \(n\) của một số nguyên dương thì số mũ \(n\) lớn nhất bằng bao nhiêu?

Input

• Chứa 3 số \(a; b; c\) mỗi số nằm trên một dòng \((a;b;c \leq 10^{12})\).

Output

• Ghi ra số \(n\) thỏa mãn yêu cầu trên.

Example

3 
3
9 

4

Một số tự nhiên được gọi là một số hồi văn nếu ta đọc từ trái sang phải hoặc từ phải sang trái đều như nhau.

Ví dụ: số \(23432\) là một số hồi văn.

Yêu cầu: Cho trước 2 số tự nhiên \(a,b\) với \(a \leq b \leq 10^{16}\). Hỏi có bao nhiêu số hồi văn \(x\) thỏa mãn \(a \leq x \leq b\).

Input

• Một dòng ghi 2 số tự nhiên \(a, b\) trên một dòng với \(a, b \leq 10^{16}\).

Output

• Ghi ra một số nguyên \(k\) là số các số hồi văn \(x\) thỏa mãn \(a \leq x \leq b\).

Example

100 191 

10