提示: 欢迎访问OurACM平台。
Problem 1907 Funny Problem

Accept: 49    Submit: 207
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Now we have a funny problem. We define the function funny(n,p) as follows:
int funny(int n, int p) { int ret = 0; while (n % p==0) { ret++; n /= p; } return ret; }
Given two positive integers a and b, three prime numbers p,q and r. Please calculate the number of n between a and b, inclusive, that satisfied funny(n,p) > funny(n,q) > funny(n,r).

Input

The first line of the input contains an integer T (T <= 30), indicating the number of cases. Each case begins with a line containing five integers a,b,p,q and r(1 <= a <= b <= 10^18, 2 <= p,q,r <= 10^9, p≠q, q≠r, p≠r, p,q and r are all primes).

Output

For each test case, print a line containing the test case number (beginning with 1) and the number of n between a and b, inclusive, that satisfied with funny(n,p) > funny(n,q) > funny(n,r).

Sample Input

1 1 50 5 2 3

Sample Output

Case 1: 1

Source

2010年全国大学生程序设计邀请赛(福州)热身赛

Submit  Back  Status  Discuss