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.|

DIRICADD - Định lý Dirichlet về cấp số cộng

 

Trong lý thuyết số, định lý Dirichlet về cấp số cộng được phát biểu một cách sơ cấp như sau:
Cho a, b là hai số nguyên dương nguyên tố cùng nhau, thế thì sẽ có vô hạn số nguyên tố có dạng a*n + b với n > 0.
Chẳng hạn với a = 4, n = 3, ta có cấp số cộng:
3, 7, 11, 15, 19, 23, 27, 31, 35, ...
Trong đó, các số nguyên tố là 3, 7, 11, 19, 23, 31, ...
Bài toán đặt ra: Cho trước a > 0, b ≥ 0, (a, b bất kì) và U ≥ L ≥ 0, nhiệm vụ của bạn là đếm xem có bao nhiêu giá trị t(n) = a*n + b là một số nguyên tố, với L ≤ n ≤ U

Trong lý thuyết số, định lý Dirichlet về cấp số cộng được phát biểu một cách sơ cấp như sau:

Cho a, b là hai số nguyên dương nguyên tố cùng nhau, thế thì sẽ có vô hạn số nguyên tố có dạng a*n + b với n > 0.

Chẳng hạn với a = 4, n = 3, ta có cấp số cộng:

3, 7, 11, 15, 19, 23, 27, 31, 35, ...

Trong đó, các số nguyên tố là 3, 7, 11, 19, 23, 31, ...

Bài toán đặt ra: Cho trước a > 0, b ≥ 0, (a, b bất kì) và U ≥ L ≥ 0, nhiệm vụ của bạn là đếm xem có bao nhiêu giá trị t(n) = a*n + b là một số nguyên tố, với L ≤ n ≤ U.

Input

Gồm nhiều test.

Mỗi bộ test gồm 4 số: a,b L, U, trong đó a*U + b ≤ 10^12, U - L ≤ 10^6.

Output

Với mỗi test, in ra như sau:

Case xxx: yyy

Trong đó, xxx là test thứ xxx, yyy là đáp số của bài toán.

Example

Input:
4 3 0 8
1 0 2 100
2 7 0 1000
0
Output:
Case 1: 6
Case 2: 25
Case 3: 301

Được gửi lên bởi:adm
Ngày:2013-01-25
Thời gian chạy:5s
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 JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.