PYTHON3

Sally has just learned about squaring numbers, and decides that a number is beautiful if it is entirely made up of digits that are themselves perfect squares. Sally throws a tantrum if she is asked to write down a number that is not beautiful. So her mother is careful to avoid asking her to do that; instead, for any given n, her mother always gives Sally the nearest beautiful number that does not exceed n. Given an integer n, help Sally's mother determine which beautiful number to present to Sally instead.

Input Format A single integer n

Constraints 0 <= n <= 10⁷

Output Format A single integer that is the largest beautiful number not exceeding n.

Sample Input 0 5

Sample Output 0 4

Explanation 0 5 is not a beautiful number because it is not a perfect square. The numbers less than 5 which are beautiful are: 0, 1 and 4. The largest of these is 4, which we return as the answer.

Sample Input 1 100

Sample Output 1 100

Explanation 1 The number 100 is already beautiful, so we return it.

Sample Input 2 2000

Sample Output 2 1999

Explanation 2 The number 2000 is not beautiful, but the integer just preceding it, 1999 is because it is made from beautiful numbers, so we return that.

#!/bin/python3

import math import os import random import re import sys

# Complete the nearestBeautiful function below in PYTHON3. def nearestBeautiful(n):