Medium Math > Number Theory

You task is to find the count of charming numbers on the given interval. The number is called charming if it is made of three various odd prime numbers. More formally the number **N** is charming if it can be represented as **P * Q * R** and **P**, **Q**, **R** are distinct odd prime numbers. Input: ------ The first line of input contains a number **T** of test cases (**1 ≤ T ≤ 100000**). Each following line represents one test case and consists of two positive numbers **L** and **R** denoting the left and right ends of the interval (**1 ≤ L ≤ R ≤ 200000000**). Output: ------- For each test case display the case number (they are numbered sequentially starting from 1) and the resulting number of charming numbers on the given interval (inclusive). Sample Input ------------ 3 1 100 1 200 199998160 199998170 Sample Output ------------- Case 1: 0 Case 2: 3 Case 3: 3 Memory Limit is very tight for this problem - 256MB. Seems like some verdict for MLE are giving RTE. Please try for memory optimized solution.

Feodor Volonter