## Odd number of divisors

Statement

## Goal

Output the number of integers between`a`and

`b`(inclusive) which have an

**odd number of unique divisors**.

**Efficient approach is required for the 2 last cases.**

Example for

`a`=1 and

`b`=4:

1 has only 1 divisor (1) => Odd number of divisors

2 has 2 divisors (1,2) => Even number of divisors

3 has 2 divisors (1,3) => Even number of divisors

4 has 3 divisors (1,2,4) => Odd number of divisors

So 1 and 4 have an odd number of divisors.

The output expected is 2.

Input

**Line 1:**Two space-separated positive integers

`a`

`b`

Output

The number of integers between

`a`and`b`(inclusive) which have an**odd number of unique divisors**.Constraints

0 <

`a`<`b`< 10^6Example

Input

1 4

Output

2

Game modes

Fastest, Shortest

Test cases

Test 1 Test

Input

1 4

Output

2

Validator 1 Validator

Input

1 8

Output

2

Test 2 Test

Input

1 12

Output

3

Validator 2 Validator

Input

1 16

Output

4

Test 3 Test

Input

16 25

Output

2

Validator 3 Validator

Input

9 25

Output

3

Test 4 Test

Input

25 900

Output

26

Validator 4 Validator

Input

36 10000

Output

95

Test 5 Test

Input

8 3601

Output

58

Validator 5 Validator

Input

50 3999

Output

56

Test 6 Test

Input

1 10000

Output

100

Validator 6 Validator

Input

4 10000

Output

99

Test 7 Test

Input

1 250000

Output

500

Validator 7 Validator

Input

9 250000

Output

498

Solution language

Solution

Stub generator input

Join the CodinGame community on Discord to chat about puzzle contributions, challenges, streams, blog articles - all that good stuff!

JOIN US ON DISCORD Online Participants