Problem 1 It is easily proved that no equilateral triangle exists with integral length sides and integral area. However, the almost equilateral triangle 5-5-6 has an area of 12 square units. We shall define an almost equilateral triangle to be a triangle for which two sides are equal and the third differs by no more than one unit. Find the sum of the perimeters of every almost equilateral triangles with integral side lengths and area and whose perimeters do not exceed one billion (1,000,000,000).

Problem 2 If a box contains twenty-one coloured discs, composed of fifteen blue discs and six red discs, and two discs were taken at random, it can be seen that the probability of taking two blue discs, P(BB) = (15/21)*(14/20) = 1/2. The next such arrangement, for which there is exactly 50% chance of taking two blue discs at random, is a box containing eighty-five blue discs and thirty-five red discs. By finding the first arrangement to contain over 10^12 = 1,000,000,000,000 discs in total, determine the number of blue discs that the box would contain.

Problem 3 Consider the fraction, n/d, where n and d are positive integers. If n < d and HCF(n,d)=1, it is called a reduced proper fraction. If we list the set of reduced proper fractions for d <= 8 in ascending order of size, we get: 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8 It can be seen that there are 3 fraction between 1/3 and 1/2. How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d <= 10,000?

Problem 4 The series, 1^1 + 2^2 + 3^3+ ... + 10^10 = 10405071317. Find the last ten digits of the series, 1^1 + 2^2 + 3^3+ ... + 1000^1000

Problem 5 The cube, 41063625 (345^3), can be permuted to produce two other cubes: 56623104 (384^3) and 66430125 (405^3). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube. Find the smallest cube for which exactly five permutations of its digits are cube.

Problem 6 Euler's Totient function, phi(n), is used to determine the number of numbers less than n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, phi(9) = 6. Interestingly, phi(87109) = 79180,and it can be seen that 87109 is a permutation of 79180. Find the value of n, below ten million, for which phi(n) is a permutation of n and the ratio n/phi(n) - produces a minimum.

Problem 7 The prime 41, can be written as the sum of six consecutive primes: 41 = 2 + 3 + 5 + 7 + 11 + 13 This is the longest sum of consecutive primes that adds to a prime below one-hundred. The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953. Which prime, below one-million, can be written as the sum of the most consecutive primes? (Integer 1 isn't prime)

Problem 8 145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145. Find the sum of all numbers which are equal to the sum of the factorial of their digits. Note: as 1! = 1 and 2! = 2 are not sums they are not included.

Problem 9 A permutaion is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are: 012, 021, 102, 120, 201, 210 What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Problem 10 By counting carefully it can be seen that a rectangular grid measuring 3 by 2 contains eighteen rectangles. Although there exists no rectangular grid that contains exactly two million rectangles, find the area of the grid with the nearest solution.

Input

There is no input for this problem.

Output

Output answer as the set of lines. On each line first is number of problem and second is answer for this problem. If any of answers will be incorrect, you'll recieve Wrong Answer.

Score

For each solved problem you'll recieve exactly one point (10 points maximum, if all problems are solved correctly).

Example

1 6174046
2 6568127473
5 806257
8 51146700

It's just the example how output would look like. If all 4 answers correct (1, 2, 5 and 8 problems), you'll recieve 4 points.