#include <stdio.h>
#include "gmp.h"

char str[1000];
mpz_t n;

//f(x) = (x^2 + 123) mod n
void f(mpz_t a){
   mpz_t result;
   mpz_init(result);
   mpz_powm_ui(result, a, 2, n);
   mpz_add_ui(result, result, 123);
   mpz_mod(a, result, n);
}

//result will be in res, n will be the number to be factored
//return 0 if can't find a factor
int pollardrho(mpz_t res, mpz_t n){
   mpz_t x, y, gcd, tmp;
   mpz_init(tmp);
   mpz_init_set_ui(x,2);
   mpz_init_set_ui(y,2);
   mpz_init_set_ui(gcd,1);
   while (mpz_cmp_ui(gcd, 1)==0){
      f(x);
      f(y);
      f(y);
      mpz_sub(tmp, x, y);
      mpz_abs(tmp,tmp);
      mpz_gcd(gcd, tmp, n);
   }
   if (mpz_cmp(gcd, n)==0)
      return 0;
   mpz_set(res, gcd);
   return 1;
}

int main(){
   scanf("%s",str);
   mpz_init(n);
   mpz_set_str(n, str, 10);
   if (pollardrho(n , n)==0)
      printf("FAILURE\n");
   else{
      mpz_get_str(str, 10, n);
      printf("Factor: %s\n", str);
   }
   return 0;
}