Người ta định nghĩa số thân thiện là những số mà nó và số đảo ngược của nó là hai số nguyên tố cùng nhau. Ví dụ: số 13 có số đảo ngược là 31 và hai số này nguyên tố cùng nhau, nên cả 13 và 31 đều là hai số thân thiện.

Cho hai số nguyên dương ~a, b~.

Yêu cầu: Hãy đếm số lượng số thân thiện nằm trong khoảng ~[a, b]~ (~a \le b~).

Input:

• Một dòng duy nhất chứa hai số nguyên dương ~a, b~ (~a \le b \le 30000~)

Output:

Ghi ra số lượng số thân thiện trong khoảng ~[a, b]~

Ví dụ:

MA_B3.INP

20 30

MA_B3.OUT

3

Cho một số nguyên dương ~N~.

Yêu cầu: Tính tổng các ước nguyên dương của ~N~.

Input:

• Một dòng duy nhất chứa số nguyên dương ~N~ (~N \le 10^{12}~)

Output:

Ghi ra tổng các ước nguyên dương của ~N~

Ví dụ:

MA_A2.INP

5

MA_A2.OUT

6

Người ta định nghĩa số thân thiện là những số mà nó và số đảo ngược của nó là hai số nguyên tố cùng nhau. Ví dụ: số 13 có số đảo ngược là 31 và hai số này nguyên tố cùng nhau, nên cả 13 và 31 đều là hai số thân thiện.

Cho hai số nguyên dương ~a, b~.

Yêu cầu: Hãy đếm số lượng số thân thiện nằm trong khoảng ~[a, b]~ (~a \le b~).

Input:

• Một dòng duy nhất chứa hai số nguyên dương ~a, b~ (~a \le b \le 30000~)

Output:

Ghi ra số lượng số thân thiện trong khoảng ~[a, b]~

Ví dụ:

MA_B3.INP

20 30

MA_B3.OUT

3

Mô tả

Người ta định nghĩa số phong phú là số mà tổng các ước nguyên dương của nó (không kể chính nó) lớn hơn chính nó.

Ví dụ:
Số 12 là số phong phú vì: 1 + 2 + 3 + 4 + 6 = 16 > 12.

Cho hai số nguyên dương a, b.

Yêu cầu

Hãy đếm số lượng số phong phú thuộc đoạn [a, b] (a ≤ b).

Input

• Gồm một dòng duy nhất chứa hai số nguyên dương a, b
• Ràng buộc: a ≤ b ≤ 10^5

Output

• In ra kết quả của bài toán.

Ví dụ

Ghi chú

• 50% số điểm có a, b ≤ 1000
• 50% số điểm còn lại không có giới hạn gì thêm

Cho ba số nguyên dương ~a, b, c~.

Yêu cầu: Đếm số lượng số nguyên dương thuộc đoạn ~[a, b]~ mà chia hết cho ~c~ (~a ≤ b~).

Input

• Gồm một dòng duy nhất chứa ba số nguyên dương ~a, b, c~ (~a, b, c ≤ 10¹⁸~).

Output

• In ra kết quả bài toán.

Ví dụ

MA_A5.INP

7 10 2

MA_A5.OUT

2

Ràng buộc

• 40% số điểm có ~a, b, c ≤ 10⁶~;
• 60% số điểm còn lại không giới hạn gì thêm.

Đề bài

Cho 4 số nguyên dương ~a, b, c, d~.

Yêu cầu: Đếm số lượng số nguyên dương thuộc đoạn ~[a, b]~ mà chia hết cho cả ~c~ và ~d~ ~(a \leq b)~.

Input

Gồm một dòng duy nhất chứa bốn số nguyên dương ~a, b, c, d~ ~(a, b, c, d \leq 10^9)~.

Output

In ra kết quả bài toán.

Ví dụ

Sample Input

1 20 2 3

Sample Output

3

Giới hạn

• Thời gian: 1s
• Bộ nhớ: 256MB
• ~40\%~ số điểm có ~a, b, c, d \leq 10^6~
• ~60\%~ số điểm còn lại không giới hạn gì thêm

Ghi chú (nếu có)

Các số chia hết cho cả ~c~ và ~d~ là các số chia hết cho ~\mathrm{lcm}(c, d)~.

Cho bốn số nguyên dương ~A,B,C,D~. Hãy đếm xem có bao nhiêu số nguyên dương ~X~ thỏa mãn các điều kiện sau:

1. ~A≤ X ≤ B~
2. ~X~ không chia hết cho ~C~;
3. ~X~ không chia hết cho ~D~;

Dữ liệu: Vào từ file văn bản CNTNUM.INP gồm:

• Một dòng duy nhất ghi bốn số ~A,B,C,D~ ~(1≤A,B≤10^{18}~; ~1≤C,D≤10^9)~.

Kết quả: Ghi ra file văn bản CNTNUM.OUT gồm:

• Một dòng duy nhất ghi số lượng số nguyên dương X thỏa mãn điều kiện của đề bài.

Ví dụ:

Sample Input 1

4 9 2 3

Sample Output 1

2

Cho dãy a gồm n số nguyên dương. Hãy cho biết có bao nhiêu cặp số trong dãy có tổng chia hết cho 3. Nói cách khác, bạn phải đếm xem có bao nhiêu cặp chỉ số ~i,j (1≤i<j≤n)~ sao cho tổng ~a_i+a_j~ chia hết cho 3.</p>

Dữ liệu: Vào từ file văn bản DIV3.INP gồm:

• Dòng 1: Một số nguyên duy nhất ~n (1≤n≤10^5)~.
• Dòng 2: Ghi n số nguyên dương ~a_1,a_2,...,a_n (1≤a_i≤10^5,∀i=1→n)~ là các phần tử của dãy.

Kết quả: Ghi ra file văn bản DIV3.OUT:

• Một dòng duy nhất ghi số lượng cặp số của dãy a có tổng chia hết cho 3.

Ví dụ:

Sample Input 1

5
3 4 2 3 4

Sample Output 1

3

Sample Input 2

4
3 6 9 12

Sample Output 2

6