Coin Payments

Our thanks to Clive Fraser for creating this problem!

In the kingdom of Erewhon all payments are made using coins. The amount of a payment can vary considerably in size. In order to accommodate this large range, the kingdom uses a large number of different coin denominations. All coin denominations are square numbers, so the Erewhon coins (in size order) have the denominations 1, 4, 9, 16, 25, 36 ... The unit of currency is the zog.

When making a payment in the kingdom of Erewhon there are two rules to be observed. The total value of the coins used must be equal to the required payment. Payment must be made such that the first coin of the payment has the largest denomination possible. The next coin in the payment must have the largest denomination possible (for the remainder of the payment) and so on until the payment is complete.

Consider a payment of 19 zogs. The largest value coin which is not greater than 19 zogs has a value of 16 zogs. The remaining 3 zogs must be paid as three 1 zog coins. So we have 19 = 16 + 1 + 1 + 1. It might seem that the payment of 19 could be made using coins with values 9 + 9 + 1. In fact this uses one coin fewer than the correct payment rule. Nevertheless, the payment rules are strictly enforced so this variation would not be accepted. The following table shows the correct coins to use for each of the payments from 19 zogs to 35 zogs inclusive. The coin count for each payment is shown in brackets.

19 = 16 + 1 + 1 + 1  (4)
20 = 16 + 4  (2)
21 = 16 + 4 + 1  (3)
22 = 16 + 4 + 1 + 1  (4)
23 = 16 + 4 + 1 + 1 + 1  (5)
24 = 16 + 4 + 4  (3)
25 = 25  (1)
26 = 25 + 1  (2)
27 = 25 + 1 + 1  (3)
28 = 25 + 1 + 1 + 1  (4)
29 = 25 + 4  (2)
30 = 25 + 4 + 1  (3)
31 = 25 + 4 + 1 + 1  (4)
32 = 25 + 4 + 1 + 1 + 1  (5)
33 = 25 + 4 + 4  (3)
34 = 25 + 9  (2)
35 = 25 + 9 + 1  (3)

If we add up the number of coins needed for each of these payments we get a total of 53 coins. This is the coin count for the range of payments from 19 to 35.

In the actual problem you will be given a range of payments from N1 to N2 inclusive. You are asked to find the coin count for this range of payments. The range given will be much larger than in this small example. However, the value of N2 will not exceed 160000000000 (16 x 10^10).

Input/Output description: The first and only line of the input data will contain two integers N1 and N2, separated by a space. Your answer is the coin count for the range of payments from N1 to N2 inclusive.

Example :

input:
19 35

answer:
53