print(next(x for x in range(30000) if pow(x, 2, 1000000) == 269696))