Problem Description
Rar the Cat has obtained a LED strip filled with N individual LED lights and wants to code them to light up in a certain manner. He at first labels the lights from 1 to N, and then lights the LEDs based on the rules below.
Initially, all the LED lights are turned off. Then for each positive integer not greater than N, (1..N), Rar the Cat toggles all the LED lights which labels are multiples of that number. Toggling a LED light means that if the light was originally on, it will now be turned off. If it was originally off, it would be turned on, akin to flipping a light switch.
As an example: When N is 10, Rar the Cat does the following steps in order:
- Initially, all the LED lights are turned off. (Off: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
- Firstly, Rar the Cat toggles all the lights that are multiples of 1. (On: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
- Secondly, Rar the Cat toggles all the lights that are multiples of 2. (On: 1, 3, 5, 7, 9 | Off: 2, 4, 6, 8, 10)
- Thirdly, Rar the Cat toggles all the lights that are multiples of 3, thereby turning LED 3 and 9 off while turning LED 6 on. (On: 1, 5, 6, 7 | Off: 2, 3, 4, 8, 9, 10)
- Fourthly, Rar the Cat toggles all the lights that are multiples of 4, thereby turning LED 4 and 8 on. (On: 1, 4, 5, 6, 7, 8 | Off: 2, 3, 9, 10)
- Then, Rar the Cat toggles all the lights that are multiples of 5, thereby turning LED 5 off while turning LED 10 on. (On: 1, 4, 6, 7, 8, 10 | Off: 2, 3, 5, 9)
- Next, Rar the Cat toggles all the lights that are multiples of 6, thereby turning LED 6 off. (On: 1, 4, 7, 8, 10 | Off: 2, 3, 5, 6, 9, 10)
- Subsequently, Rar the Cat toggles all the lights that are multiples of 7, thereby turning LED 7 off. (On: 1, 4, 8, 10 | Off: 2, 3, 5, 6, 7, 9)
- After that, Rar the Cat toggles all the lights that are multiples of 8, thereby turning LED 8 off. (On: 1, 4, 10 | Off: 2, 3, 5, 6, 7, 8, 9)
- Finally, Rar the Cat toggles all the lights that are multiples of 9, thereby turning LED 9 on. (On: 1, 4, 9, 10 | Off: 2, 3, 5, 6, 7, 8)
- Lastly, Rar the Cat toggles all the lights that are multiples of 10, thereby turning LED 10 off. (On: 1, 4, 9 | Off: 2, 3, 5, 6, 7, 8, 10)
Rar the Cat would like to know how many LED lights are turned on in the LED strip at the end of the day.
Input
Input consists of a single integer, N.
Output
A single integer, denoting how many LED lights are switched on in the LED strip at the end of the day.
Limits
Subtask 1 (9%): 0 < N ≤ 10
Subtask 2 (32%): 0 < N ≤ 1000
Subtask 3 (34%): 0 < N ≤ 1000000
Subtask 4 (25%): 0 < N ≤ 1018 (Please use long long to input)
Subtask 5 (0%): As per sample testcases.
Sample Testcase 1
Input:
10
Output:
3
Sample Testcase 2
This testcase adheres to the limits of subtask 2 to 4 only.
Input:
1000
Output:
31
Sample Testcase 3
This testcase adheres to the limits of subtask 3 and 4 only.
Input:
1000000
Output:
1000
Sample Testcase 4
This testcase adheres to the limits of subtask 4 only.
Input:
964785235727023492
Output:
982234817