# DCP-513: Charming Numbers Back to All Problems

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.

### Problem Limits

 Language Time Limit (seconds) C 2.00 C++ 2.00 C++14 2.00 C# 4.00 Go 4.00 Java 4.00 JavaScript 4.00 Objective-C 4.00 Perl 4.00 PHP 4.00 Python 4.00 Python3 4.00 Ruby 4.00 VB.Net 4.00

# 16/193

Solve/Submission

### Ranking

# User Language Timing
01 feodorv C 1.47s
02 rayhan50001 Cpp14 1.50s
03 rajdipsaha Cpp 1.81s
04 tariqiitju Cpp14 2.00s
05 cjoa Cpp 2.51s
06 Tourist Cpp14 3.05s
07 Informatimukas Cpp 3.57s