We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #72: Counting fractions

Project Euler #72: Counting fractions

Problem
Submissions
Leaderboard
Discussions

This problem is a programming version of Problem 72 from projecteuler.net

Consider the fraction, , where and are positive integers. If and , it is called a reduced proper fraction.

If we list the set of reduced proper fractions for in ascending order of size, we get:

It can be seen that there are elements in this set.

How many elements would be contained in the set of reduced proper fractions for ?

Input Format

First line contains , number of test cases. lines follow
Each line contains 1 integer

Constraints


Output Format

Print the result corresponding to each testcase on a new line.

Sample Input

2
8
5

Sample Output

21
9

Author

shashank21j

Difficulty

Easy

Max Score

100

Submitted By

1421

Need Help?


View discussions
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature