All Tracks Math Number Theory Basic Number Theory-1 Problem

Gotta Catch 'Em All

Easy, Prime Factorization, Sorting


In Pallet town of Kanto region, there lived a young boy named Ash Ketchum. Ash loves Pokemon and has a dream of becoming a Pokemon Master. He is about to start his Pokemon journey so he reaches to Professor Oak to get his first starter Pokemon. Before giving Ash his starter Pokemon, Professor Oak needs to check whether he is capable of raising a Pokemon or not. So, the professor gave him a task to test his knowledge about Pokemon. The task is as follows:

Each Pokemon can be represented by a unique ID number and its strength is equivalent to the total number of factors (including 1 and number itself) of its ID number. In a Pokemon battle, a Pokemon with higher strength will always win a battle against a Pokemon with lower strength. Let the total number of Pokemon's in Kanto region be N(their ID ranging from 1 to N). Given a Pokemon ID number K. Find the total number of Pokemon, the given Pokemon can certainly beat.

Input Format:
First line of input contains space separated T and N, where T denotes the total number of test cases.
Each test case contains an integer K.

Output Format:
For every test case, output the correct answer in new line.

1 ≤ T ≤ 105
1 ≤ N ≤ 106
1 ≤ K ≤ N

2 8

For N = 8, strength distribution of every Pokemon is given corresponding to its ID number where strength is equal to the number of factors of ID number. For example- Pokemon with ID no. 8 has strength equal to 4 (Factors of 8 are 1, 2, 4, 8).

ID No.     Strength
  1       1
  2       2
  3       2
  4       3
  5       2
  6       4
  7       2
  8       4

Sample Test Case 1: For K = 3, Pokemon with ID no. 3 has strength equal to 2. It can only defeat Pokemon with ID no. 1. Therefore, the answer is 1.

Sample Test Case 2 : For K = 4, Pokemon with ID no. 4 has strength equal to 3. It can defeat Pokemon with ID no. 1, 2, 3, 5 and 7. Therefore, the answer is 5.

Time Limit: 0.5 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in

SKIT, Jaipur

Challenge Name

Code Emblaze

View All Notifications