### Problem Statement

A non-negative integer n is said to be a sum of two perfect powers if there exist two non-negative integers a and b such that am + bk = n for some positive integers m and k, both greater than 1. Given two non-negative integers lowerBound and upperBound, return the number of integers between lowerBound and upperBound, inclusive, that are sums of two perfect powers.

### Definition

 Class: SumsOfPerfectPowers Method: howMany Parameters: int, int Returns: int Method signature: int howMany(int lowerBound, int upperBound) (be sure your method is public)

### Constraints

-lowerBound will be between 0 and 5000000, inclusive.
-upperBound will be between lowerBound and 5000000, inclusive.

### Examples

0)

 `0` `1`
`Returns: 2`
 0 and 1 are both sums of two perfect powers since 0 = 0 + 0 and 1 = 12 + 02.
1)

 `5` `6`
`Returns: 1`
 5 is a sum of two perfect powers since 5 = 22 + 12 while 6 is not.
2)

 `25` `30`
`Returns: 5`
 Only 30 is not a sum of two perfect powers.
3)

 `103` `103`
`Returns: 0`
 There may be no desired integers in the range.
4)

 `1` `100000`
`Returns: 33604`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7613

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10674&pm=7613

Xixas

#### Testers:

PabloGilberto , brett1479 , Olexiy , ged

#### Problem categories:

Simple Math, Simple Search, Iteration