Problem: Integer factorisation is hard. The RSA Factoring Challenge offered $100 000 for factoring RSA-1024, a 1024-bit long product of two prime numbers. To this date, nobody was able to claim the prize. We want you to factorise a 1024-bit number.

Since your programming language of choice might not offer facilities for handling large integers, we will provide you with a very simple calculator. 

To use this calculator, you can print queries on the standard output and retrieve the results from the standard input. The operations are as follows: 

  * + x y where x and y are integers between 0 and n-1. Returns (x+y) mod n. 
  * - x y where x and y are integers between 0 and n-1. Returns (x-y) mod n. 
  * * x y where x and y are integers between 0 and n-1. Returns (x ⋅ y) mod n. 
  * / x y where x and y are integers between 0 and n-1 and y is coprime with n. Returns (x ⋅ y^{-1}) mod n where y^{-1} is multiplicative inverse of y modulo n. If y is not coprime with n, then -1 is returned instead. 
  * sqrt x where x is integer between 0 and n-1 coprime with n. Returns y such that y^2 mod n = x. If there are multiple such integers, only one of them is returned. If there are none, -1 is returned instead. 
  * ^ x y where x and y are integers between 0 and n-1. Returns {x^y mod n}. 



Find the factorisation of n that is a product of between 2 and 10 distinct prime numbers, all of form 4x + 3 for some integer x.

Because of technical issues, we restrict number of requests to 100.

Input

The only line contains a single integer n (21 ≤ n ≤ 2^{1024}). It is guaranteed that n is a product of between 2 and 10 distinct prime numbers, all of form 4x + 3 for some integer x.

Output

You can print as many queries as you wish, adhering to the time limit (see the Interaction section for more details). 

When you think you know the answer, output a single line of form ! k p_1 p_2 ... p_k, where k is the number of prime factors of n, and p_i are the distinct prime factors. You may print the factors in any order.

Hacks input

For hacks, use the following format:. 

The first should contain k (2 ≤ k ≤ 10) — the number of prime factors of n. 

The second should contain k space separated integers p_1, p_2, ..., p_k (21 ≤ n ≤ 2^{1024}) — the prime factors of n. All prime factors have to be of form 4x + 3 for some integer x. They all have to be distinct. 

Interaction

After printing a query do not forget to output end of line and flush the output. Otherwise you will get Idleness limit exceeded. To do this, use:

  * fflush(stdout) or cout.flush() in C++;
  * System.out.flush() in Java;
  * flush(output) in Pascal;
  * stdout.flush() in Python;
  * see documentation for other languages.



The number of queries is not limited. However, your program must (as always) fit in the time limit. The run time of the interactor is also counted towards the time limit. The maximum runtime of each query is given below.

  * + x y — up to 1 ms. 
  * - x y — up to 1 ms. 
  * * x y — up to 1 ms. 
  * / x y — up to 350 ms. 
  * sqrt x — up to 80 ms. 
  * ^ x y — up to 350 ms. 



Note that the sample input contains extra empty lines so that it easier to read. The real input will not contain any empty lines and you do not need to output extra empty lines.

Example

Input

21

7

17

15

17

11

-1

15



Output

+ 12 16

- 6 10

* 8 15

/ 5 4

sqrt 16

sqrt 5

^ 6 12

! 2 3 7

Note

We start by reading the first line containing the integer n = 21. Then, we ask for: 

  1. (12 + 16) mod 21 = 28 mod 21 = 7. 
  2. (6 - 10) mod 21 = -4 mod 21 = 17. 
  3. (8 ⋅ 15) mod 21 = 120 mod 21 = 15. 
  4. (5 ⋅ 4^{-1}) mod 21 = (5 ⋅ 16) mod 21 = 80 mod 21 = 17. 
  5. Square root of 16. The answer is 11, as (11 ⋅ 11) mod 21 = 121 mod 21 = 16. Note that the answer may as well be 10. 
  6. Square root of 5. There is no x such that x^2 mod 21 = 5, so the output is -1. 
  7. (6^{12}) mod 21 = 2176782336 mod 21 = 15. 



We conclude that our calculator is working, stop fooling around and realise that 21 = 3 ⋅ 7.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
unsigned long long gcd(unsigned long long a, unsigned long long b) {
  return b == 0 ? a : gcd(b, a % b);
}
const int BIGINTBITS = 32;
const unsigned int BIGINTMASK = (1LL << BIGINTBITS) - 1;
struct BigInt {
  vector<unsigned int> d;
  BigInt() {}
  BigInt(unsigned long long x) {
    while (x != 0) d.push_back(x & BIGINTMASK), x >>= BIGINTBITS;
  }
  unsigned long long val() const {
    unsigned long long ret = 0;
    for (int i = ((int)(d).size()) - 1; i >= 0; --i)
      ret = (ret << BIGINTBITS) | d[i];
    return ret;
  }
};
void normalize(BigInt &a) {
  while (((int)(a.d).size()) > 0 && a.d[((int)(a.d).size()) - 1] == 0)
    a.d.pop_back();
}
int cmp(const BigInt &a, const BigInt &b) {
  if (((int)(a.d).size()) != ((int)(b.d).size()))
    return ((int)(a.d).size()) < ((int)(b.d).size()) ? -1 : +1;
  for (int i = ((int)(a.d).size()) - 1; i >= 0; --i)
    if (a.d[i] != b.d[i]) return a.d[i] < b.d[i] ? -1 : +1;
  return 0;
}
bool operator<(const BigInt &a, const BigInt &b) { return cmp(a, b) < 0; }
bool operator<=(const BigInt &a, const BigInt &b) { return cmp(a, b) <= 0; }
bool operator==(const BigInt &a, const BigInt &b) { return cmp(a, b) == 0; }
BigInt &operator+=(BigInt &a, const BigInt &b) {
  unsigned long long carry = 0;
  for (int i = 0; i < ((int)(b.d).size()) || carry != 0; ++i) {
    if (i < ((int)(a.d).size()))
      carry += a.d[i];
    else
      a.d.push_back(0);
    if (i < ((int)(b.d).size())) carry += b.d[i];
    a.d[i] = carry & BIGINTMASK;
    carry >>= BIGINTBITS;
  }
  return a;
}
BigInt operator+(const BigInt &a, const BigInt &b) {
  BigInt ret = a;
  ret += b;
  return ret;
}
BigInt &operator-=(BigInt &a, const BigInt &b) {
  unsigned long long carry = 0;
  for (int i = 0; i < ((int)(b.d).size()) || carry != 0; ++i) {
    if (i < ((int)(b.d).size())) carry += b.d[i];
    assert(i < ((int)(a.d).size()));
    if (carry <= a.d[i])
      a.d[i] -= carry, carry = 0;
    else
      a.d[i] += (1LL << BIGINTBITS) - carry, carry = 1;
  }
  normalize(a);
  return a;
}
BigInt operator-(const BigInt &a, const BigInt &b) {
  BigInt ret = a;
  ret -= b;
  return ret;
}
BigInt operator*(const BigInt &a, const BigInt &b) {
  BigInt ret;
  for (int j = 0; j < ((int)(b.d).size()); ++j) {
    unsigned long long carry = 0;
    for (int i = 0; i < ((int)(a.d).size()) || carry != 0; ++i) {
      if (i < ((int)(a.d).size())) carry += (unsigned long long)a.d[i] * b.d[j];
      if (i + j < ((int)(ret.d).size()))
        carry += ret.d[i + j];
      else
        ret.d.push_back(0);
      ret.d[i + j] = carry & BIGINTMASK;
      carry >>= BIGINTBITS;
    }
  }
  return ret;
}
BigInt operator*(const BigInt &a, const unsigned int &b) {
  assert(0 <= b && b <= BIGINTMASK);
  unsigned long long carry = 0;
  BigInt ret;
  if (b == 0) return ret;
  for (int i = 0; i < ((int)(a.d).size()) || carry != 0; ++i) {
    if (i < ((int)(a.d).size())) carry += (unsigned long long)a.d[i] * b;
    if (i < ((int)(ret.d).size()))
      carry += ret.d[i];
    else
      ret.d.push_back(0);
    ret.d[i] = carry & BIGINTMASK;
    carry >>= BIGINTBITS;
  }
  return ret;
}
BigInt operator<<(const BigInt &a, const int &shift) {
  assert(shift < BIGINTBITS);
  BigInt ret;
  unsigned long long carry = 0;
  for (int i = 0; i < ((int)(a.d).size()) || carry != 0; ++i) {
    if (i < ((int)(a.d).size())) carry |= ((unsigned long long)a.d[i]) << shift;
    ret.d.push_back(carry & BIGINTMASK);
    carry >>= BIGINTBITS;
  }
  return ret;
}
BigInt operator>>(const BigInt &a, const int &shift) {
  assert(shift < BIGINTBITS);
  BigInt ret;
  unsigned long long carry = 0;
  for (int i = 0; i < ((int)(a.d).size()) || carry != 0; ++i) {
    if (i < ((int)(a.d).size()))
      carry |= ((unsigned long long)a.d[i]) << (BIGINTBITS - shift);
    if (i != 0) ret.d.push_back(carry & BIGINTMASK);
    carry >>= BIGINTBITS;
  }
  return ret;
}
void dividewithremainder(const BigInt &a, const unsigned int &b, BigInt &q,
                         unsigned int &r) {
  assert(1 <= b && b <= BIGINTMASK);
  q.d.resize(((int)(a.d).size()));
  unsigned long long carry = 0;
  for (int i = ((int)(a.d).size()) - 1; i >= 0; --i) {
    carry <<= BIGINTBITS;
    carry += a.d[i];
    q.d[i] = carry / b;
    carry -= (unsigned long long)q.d[i] * b;
  }
  normalize(q);
  r = carry;
}
BigInt operator/(const BigInt &a, const unsigned int &b) {
  BigInt q;
  unsigned int r;
  dividewithremainder(a, b, q, r);
  return q;
}
unsigned int operator%(const BigInt &a, const unsigned int &b) {
  BigInt q;
  unsigned int r;
  dividewithremainder(a, b, q, r);
  return r;
}
void dividewithremainder(const BigInt &a, const BigInt &b, BigInt &q,
                         BigInt &r) {
  if (a < b) {
    q.d.clear();
    r = a;
    return;
  }
  if (((int)(b.d).size()) == 1) {
    unsigned int rr;
    dividewithremainder(a, b.d[0], q, rr);
    r = BigInt(rr);
    return;
  }
  int shift = 0;
  while (((b.d[((int)(b.d).size()) - 1] >> (BIGINTBITS - shift - 1)) & 1) == 0)
    ++shift;
  BigInt u = a << shift, v = b << shift;
  q.d.resize(((int)(u.d).size()) - ((int)(v.d).size()) + 1);
  r.d.resize(((int)(v.d).size()));
  for (int i = 0; i < ((int)(v.d).size()); ++i)
    r.d[((int)(v.d).size()) - i - 1] = u.d[((int)(u.d).size()) - i - 1];
  for (int i = ((int)(q.d).size()) - 1; i >= 0; --i) {
    unsigned long long num1 = ((int)(v.d).size()) < ((int)(r.d).size())
                                  ? r.d[((int)(v.d).size())]
                                  : 0,
                       num2 = ((int)(v.d).size()) - 1 < ((int)(r.d).size())
                                  ? r.d[((int)(v.d).size()) - 1]
                                  : 0;
    unsigned long long num = (num1 << BIGINTBITS) | num2;
    unsigned int den = v.d[((int)(v.d).size()) - 1];
    unsigned int guess = min(num / den, (unsigned long long)BIGINTMASK);
    while (r < v * guess) --guess;
    q.d[i] = guess;
    r -= v * guess;
    if (i != 0) r.d.insert(r.d.begin(), u.d[i - 1]);
  }
  normalize(q);
  r = r >> shift;
}
BigInt operator/(const BigInt &a, const BigInt &b) {
  BigInt q, r;
  dividewithremainder(a, b, q, r);
  return q;
}
BigInt operator%(const BigInt &a, const BigInt &b) {
  BigInt q, r;
  dividewithremainder(a, b, q, r);
  return r;
}
BigInt _parse(const string &s, int offset, int k, const vector<BigInt> &xs) {
  if (k == 0)
    return BigInt(0 <= offset && offset < ((int)(s).size()) ? s[offset] - '0'
                                                            : 0);
  return _parse(s, offset, k - 1, xs) * xs[k] +
         _parse(s, offset + (1 << (k - 1)), k - 1, xs);
}
BigInt parse(const string &s) {
  int k = 0;
  while ((1 << k) < ((int)(s).size())) ++k;
  vector<BigInt> xs;
  xs.push_back(BigInt(1));
  xs.push_back(BigInt(10));
  while (k >= ((int)(xs).size())) xs.push_back(xs.back() * xs.back());
  return _parse(s, ((int)(s).size()) - (1 << k), k, xs);
}
template <typename T>
constexpr T constsqr(T a) {
  return a * a;
}
template <typename T>
constexpr T constpower(T a, std::size_t n) {
  return n == 0 ? 1 : constsqr(constpower(a, n / 2)) * (n % 2 == 0 ? 1 : a);
}
const int BIGDECIMALDIGITS = 9;
const int BIGDECIMALBASE = constpower(10, BIGDECIMALDIGITS);
struct BigDecimal {
  vector<int> d;
  BigDecimal() {}
  BigDecimal(unsigned long long x) {
    while (x > 0) d.push_back(x % BIGDECIMALBASE), x /= BIGDECIMALBASE;
  }
};
BigDecimal &operator+=(BigDecimal &a, const BigDecimal &b) {
  long long carry = 0;
  for (int i = 0; i < ((int)(b.d).size()) || carry != 0; ++i) {
    if (i < ((int)(a.d).size()))
      carry += a.d[i];
    else
      a.d.push_back(0);
    if (i < ((int)(b.d).size())) carry += b.d[i];
    a.d[i] = carry % BIGDECIMALBASE;
    carry /= BIGDECIMALBASE;
  }
  return a;
}
BigDecimal operator+(const BigDecimal &a, const BigDecimal &b) {
  BigDecimal ret = a;
  ret += b;
  return ret;
}
BigDecimal operator*(const BigDecimal &a, const BigDecimal &b) {
  BigDecimal ret;
  for (int j = 0; j < ((int)(b.d).size()); ++j) {
    long long carry = 0;
    for (int i = 0; i < ((int)(a.d).size()) || carry != 0; ++i) {
      if (i < ((int)(a.d).size())) carry += (long long)a.d[i] * b.d[j];
      if (i + j < ((int)(ret.d).size()))
        carry += ret.d[i + j];
      else
        ret.d.push_back(0);
      ret.d[i + j] = carry % BIGDECIMALBASE;
      carry /= BIGDECIMALBASE;
    }
  }
  return ret;
}
BigDecimal _format(const BigInt &a, int offset, int k,
                   const vector<BigDecimal> &xs) {
  if (k == 0)
    return BigDecimal(0 <= offset && offset < ((int)(a.d).size()) ? a.d[offset]
                                                                  : 0);
  return _format(a, offset, k - 1, xs) * xs[k] +
         _format(a, offset - (1 << (k - 1)), k - 1, xs);
}
string format(const BigInt &a) {
  int k = 0;
  while ((1 << k) < ((int)(a.d).size())) ++k;
  vector<BigDecimal> xs;
  xs.push_back(BigDecimal(1));
  xs.push_back(BigDecimal(1LL << BIGINTBITS));
  while (k >= ((int)(xs).size())) xs.push_back(xs.back() * xs.back());
  BigDecimal ans = _format(a, (1 << k) - 1, k, xs);
  if (((int)(ans.d).size()) == 0) return "0";
  string ret(((int)(ans.d).size()) * BIGDECIMALDIGITS, '?');
  for (int i = (0); i < (((int)(ans.d).size())); ++i)
    sprintf(&ret[0] + i * BIGDECIMALDIGITS, "%0*d", BIGDECIMALDIGITS,
            ans.d[((int)(ans.d).size()) - i - 1]);
  int nzero = 0;
  while (nzero < ((int)(ret).size()) && ret[nzero] == '0') ++nzero;
  ret = ret.substr(nzero);
  return ret;
}
BigInt gcd(const BigInt &a, const BigInt &b) {
  return ((int)(b.d).size()) == 0 ? a : gcd(b, a % b);
}
void extractleadingbits(const BigInt &p, const BigInt &q, unsigned long long &x,
                        unsigned long long &y) {
  x = (((unsigned long long)p.d[((int)(p.d).size()) - 1]) << BIGINTBITS) |
      p.d[((int)(p.d).size()) - 2];
  y = (((unsigned long long)(((int)(q.d).size()) == ((int)(p.d).size())
                                 ? q.d[((int)(p.d).size()) - 1]
                                 : 0))
       << BIGINTBITS) |
      q.d[((int)(p.d).size()) - 2];
  if (((int)(p.d).size()) == 2) return;
  int shift = 0;
  while (((x >> (2 * BIGINTBITS - shift - 1)) & 1) == 0) ++shift;
  if (shift == 0) return;
  x = (x << shift) | (p.d[((int)(p.d).size()) - 3] >> (BIGINTBITS - shift)),
  y = (y << shift) | (q.d[((int)(p.d).size()) - 3] >> (BIGINTBITS - shift));
}
BigInt lehmergcd(BigInt p, BigInt q) {
  int cmpres = cmp(p, q);
  if (cmpres == 0) return p;
  if (cmpres < 0) swap(p, q);
  unsigned long long x, y, z, num1, den1, w1, num2, den2, w2, e, f, xn, yn, t;
  unsigned int a, b, c, d, w;
  bool needlongdiv;
  int parity;
  int nlong = 0, nlehmer = 0, clehmer, nit = 0;
  while (true) {
    if (((int)(q.d).size()) == 0)
      return p;
    else if (((int)(p.d).size()) <= 2)
      break;
    else
      needlongdiv = false;
    if (((int)(p.d).size()) - ((int)(q.d).size()) >= 2) needlongdiv = true;
    if (!needlongdiv) {
      extractleadingbits(p, q, x, y);
      if (y <= BIGINTMASK || x == y) needlongdiv = true;
      if (x == ((((unsigned long long)BIGINTMASK) << BIGINTBITS) | BIGINTMASK))
        x >>= 1, y >>= 1;
    }
    if (!needlongdiv) {
      num1 = x, den1 = y + 1, num2 = x + 1, den2 = y, w1 = num1 / den1,
      w2 = num2 / den2;
      if (w1 != w2 || w1 > BIGINTMASK)
        needlongdiv = true;
      else
        w = w1;
    }
    if (!needlongdiv) {
      a = 0, b = 1, c = 1, d = w, z = x - w * y, x = y, y = z, parity = 0,
      clehmer = 1;
      while (true) {
        if (parity == 0) {
          if (y == d) break;
          num1 = x - a, den1 = y + c, num2 = x + b, den2 = y - d;
        }
        if (parity == 1) {
          if (y == c) break;
          num1 = x - b, den1 = y + d, num2 = x + a, den2 = y - c;
        }
        w1 = num1 / den1, w2 = num2 / den2;
        if (w1 != w2 || w1 > BIGINTMASK)
          break;
        else
          w = w1;
        e = a + w * c, f = b + w * d, z = x - w * y;
        if (e > BIGINTMASK || f > BIGINTMASK)
          break;
        else
          a = c, c = e, b = d, d = f, x = y, y = z, parity = 1 - parity,
          ++clehmer;
      }
    }
    if (!needlongdiv && b != 0) {
      x = 0, y = 0, xn = 0, yn = 0, nlehmer += clehmer, ++nit;
      while (((int)(q.d).size()) < ((int)(p.d).size())) q.d.push_back(0);
      for (int i = 0; i < ((int)(p.d).size()); ++i) {
        unsigned long long cp = p.d[i], cq = q.d[i];
        if (parity == 0)
          x += cq * b, xn += cp * a, y += cp * c, yn += cq * d;
        else
          x += cp * a, xn += cq * b, y += cq * d, yn += cp * c;
        t = min(x, xn), x -= t, xn -= t, t = min(y, yn), y -= t, yn -= t;
        if (xn == 0)
          p.d[i] = x & BIGINTMASK, x >>= BIGINTBITS;
        else if ((xn & BIGINTMASK) == 0)
          p.d[i] = 0, xn >>= BIGINTBITS;
        else
          p.d[i] = BIGINTMASK - (xn & BIGINTMASK) + 1, xn >>= BIGINTBITS, ++xn;
        if (yn == 0)
          q.d[i] = y & BIGINTMASK, y >>= BIGINTBITS;
        else if ((yn & BIGINTMASK) == 0)
          q.d[i] = 0, yn >>= BIGINTBITS;
        else
          q.d[i] = BIGINTMASK - (yn & BIGINTMASK) + 1, yn >>= BIGINTBITS, ++yn;
      }
      assert(x == 0 && y == 0 && xn == 0 && yn == 0);
      normalize(p);
      normalize(q);
    } else {
      BigInt r = p % q;
      p = q, q = r;
      ++nlong, ++nit;
    }
  }
  x = (((unsigned long long)(((int)(p.d).size()) == 2 ? p.d[1] : 0))
       << BIGINTBITS) |
      p.d[0];
  y = (((unsigned long long)(((int)(q.d).size()) == 2 ? q.d[1] : 0))
       << BIGINTBITS) |
      q.d[0];
  while (y != 0) {
    z = x % y, x = y, y = z;
  }
  return BigInt(x);
}
int bitcnt(const BigInt &x) {
  if (((int)(x.d).size()) == 0) return 0;
  int r = 0;
  while (x.d[((int)(x.d).size()) - 1] >= (1ULL << r)) ++r;
  return (((int)(x.d).size()) - 1) * BIGINTBITS + r;
}
BigInt randbits(int nbits, mt19937 &rnd) {
  BigInt ret;
  int ndigs = (nbits + BIGINTBITS - 1) / BIGINTBITS;
  for (int i = (0); i < (ndigs - 1); ++i) ret.d.push_back(rnd());
  ret.d.push_back(rnd() % (1ULL << (nbits - (ndigs - 1) * BIGINTBITS)));
  normalize(ret);
  return ret;
}
BigInt pw(BigInt x, BigInt n, BigInt mod) {
  BigInt ret(1);
  for (int i = (0); i < (((int)(n.d).size()) * BIGINTBITS); ++i) {
    if ((n.d[i / BIGINTBITS] & (1ULL << (i % BIGINTBITS))) != 0)
      ret = ret * x % mod;
    x = x * x % mod;
  }
  return ret;
}
bool isprobableprime(const BigInt &n, mt19937 &rnd) {
  if (((int)(n.d).size()) == 1 && (n.d[0] == 2 || n.d[0] == 3)) return true;
  if (((int)(n.d).size()) == 0 || ((int)(n.d).size()) == 1 && n.d[0] == 1 ||
      (n.d[0] & 1) == 0)
    return false;
  BigInt d = n - 1;
  int r = 0;
  while (d.d[0] == 0) r += BIGINTBITS, d.d.erase(d.d.begin());
  int rr = 0;
  while ((d.d[0] & (1 << rr)) == 0) ++rr;
  r += rr;
  d = d >> rr;
  BigInt alo = 2, ahi = n - 2;
  int ahibits = bitcnt(ahi);
  BigInt xlo = 1, xhi = n - 1;
  for (int k = (0); k < (4); ++k) {
    BigInt a;
    while (true) {
      a = randbits(ahibits, rnd);
      if (alo <= a && a <= ahi) break;
    }
    BigInt x = pw(a, d, n);
    if (x == xlo || x == xhi) continue;
    bool ok = false;
    for (int i = (0); i < (r - 1); ++i) {
      x = x * x % n;
      if (x == xhi) {
        ok = true;
        break;
      }
    }
    if (ok) continue;
    return false;
  }
  return true;
}
bool local = false;
vector<BigInt> ploc;
BigInt nloc;
mt19937 locrnd;
BigInt egcd(BigInt a, BigInt b, BigInt &x, bool &xneg, BigInt &y, bool &yneg) {
  if (b == 0) {
    x = 1, xneg = false, y = 0, yneg = false;
    return a;
  }
  BigInt g = egcd(b, a % b, y, yneg, x, xneg);
  BigInt z = x * (a / b);
  if (xneg != yneg)
    y += z;
  else if (z <= y)
    y -= z;
  else
    y = z - y, yneg = !yneg;
  return g;
}
pair<BigInt, BigInt> invcrt(BigInt a1, BigInt mod1, BigInt a2, BigInt mod2) {
  if (a2 < a1) swap(a1, a2), swap(mod1, mod2);
  bool c1neg, c2neg;
  BigInt c1, c2, g = egcd(mod1, mod2, c1, c1neg, c2, c2neg);
  assert((a2 - a1) % g == 0);
  BigInt t = (a2 - a1) / g, lcm = mod1 / g * mod2;
  if (c1neg) c1 = mod2 - c1;
  BigInt x = (a1 + c1 * t % (mod2 / g) * mod1) % lcm;
  return make_pair(x, lcm);
}
pair<BigInt, BigInt> invcrt(vector<BigInt> a, vector<BigInt> mod) {
  pair<BigInt, BigInt> ret = make_pair(a[0], mod[0]);
  for (int i = (1); i < (((int)(a).size())); ++i)
    ret = invcrt(ret.first, ret.second, a[i], mod[i]);
  return ret;
}
BigInt query(BigInt x) {
  if (!local) {
    printf("sqrt %s\n", format(x).c_str());
    fflush(stdout);
    string s;
    cin >> s;
    assert(s != "-1");
    return parse(s);
  } else {
    vector<BigInt> a;
    for (int i = (0); i < (((int)(ploc).size())); ++i) {
      BigInt cx = x % ploc[i];
      BigInt cy = pw(cx, (ploc[i] + 1) / 4, ploc[i]);
      if (locrnd() % 2 == 1) cy = ploc[i] - cy;
      BigInt A = cy * cy % ploc[i], B = cx;
      assert(cy * cy % ploc[i] == cx);
      a.push_back(cy);
    }
    BigInt ret = invcrt(a, ploc).first;
    assert(ret * ret % nloc == x);
    return ret;
  }
}
vector<BigInt> ans;
void solve(const string &s) {
  std::mt19937 rnd(
      (int)std::chrono::steady_clock::now().time_since_epoch().count());
  BigInt n = parse(s);
  ans.clear();
  vector<BigInt> comp;
  comp.push_back(n);
  while (((int)(comp).size()) > 0) {
    BigInt x;
    while (true) {
      x.d.clear();
      for (int i = (0); i < (((int)(n.d).size()) - 1); ++i)
        x.d.push_back(rnd());
      int mxbit = 0;
      while (n.d[((int)(n.d).size()) - 1] >= (2ULL << mxbit)) ++mxbit;
      x.d.push_back(rnd() % (2ULL << mxbit));
      normalize(x);
      if (x < n) break;
    }
    BigInt y = x * x % n;
    BigInt z = query(y);
    if (z == x || z == n - x) continue;
    BigInt d = (x + z) % n;
    vector<BigInt> ncomp;
    for (int i = (0); i < (((int)(comp).size())); ++i) {
      BigInt g = lehmergcd(comp[i], d);
      if (g == 1 || g == comp[i])
        ncomp.push_back(comp[i]);
      else {
        BigInt gg = comp[i] / g;
        (isprobableprime(g, rnd) ? ans : comp).push_back(g),
            (isprobableprime(gg, rnd) ? ans : comp).push_back(gg);
      }
    }
    comp = ncomp;
  }
  sort(ans.begin(), ans.end());
}
void run() {
  string s;
  cin >> s;
  solve(s);
  printf("! %d", ((int)(ans).size()));
  for (int i = (0); i < (((int)(ans).size())); ++i)
    printf(" %s", format(ans[i]).c_str());
  fflush(stdout);
}
void stressdivsmall() {
  printf("\nstressdivsmall\n");
  for (int rep = (0); rep < (1000000); ++rep) {
    int ydig = rand() % 32 + 1;
    unsigned long long y = 0;
    for (int i = (0); i < (ydig); ++i) y = (y << 1) + rand() % 2;
    if (y == 0) continue;
    int xdig = rand() % (2 * ydig) + 1;
    unsigned long long x = 0;
    for (int i = (0); i < (xdig); ++i) x = (x << 1) + rand() % 2;
    BigInt a(x), b(y), c = a / b;
    unsigned long long have = c.val(), want = x / y;
    if (have == want) {
      if (rep % 1000 == 999) printf(".");
      continue;
    }
    printf("rep%d: %llu/%llu -> have=%llu want=%llu\n", rep, x, y, have, want);
    break;
  }
}
void stressdivlarge() {
  printf("\nstressdivlarge\n");
  for (int rep = (0); rep < (1000); ++rep) {
    BigInt a;
    a.d.resize((1000 + BIGINTBITS - 1) / BIGINTBITS);
    for (int i = (0); i < (((int)(a.d).size())); ++i)
      for (int j = (0); j < (BIGINTBITS); ++j) a.d[i] |= (rand() % 2) << j;
    normalize(a);
    BigInt b;
    b.d.resize((((int)(a.d).size()) + 1) / 2);
    for (int i = (0); i < (((int)(b.d).size())); ++i)
      for (int j = (0); j < (BIGINTBITS); ++j) b.d[i] |= (rand() % 2) << j;
    normalize(b);
    if (((int)(b.d).size()) == 0) continue;
    BigInt c = a / b;
    BigInt d = a - b * c;
    if (d < b) {
      printf(".");
      continue;
    }
    printf("err\n");
  }
}
void stressparse() {
  printf("\nverifying small\n");
  for (int rep = (0); rep < (100); ++rep) {
    int len = rand() % 18 + 1;
    string s(len, '?');
    for (int i = (0); i < (len); ++i) s[i] = '0' + rand() % 10;
    while (((int)(s).size()) > 1 && s[0] == '0') s = s.substr(1);
    BigInt a = parse(s);
    unsigned long long havenum = a.val(), wantnum;
    sscanf(s.c_str(), "%llu", &wantnum);
    if (havenum != wantnum) {
      printf("err %s => havenum=%llu wantnum=%llu\n", s.c_str(), havenum,
             wantnum);
      return;
    }
    string havestr = format(a), wantstr = s;
    if (havestr != wantstr) {
      printf("err %s => havestr=%s wantstr=%s\n", s.c_str(), havestr.c_str(),
             wantstr.c_str());
      return;
    }
    printf(".");
  }
  printf("\ntesting large\n");
  for (int rep = (0); rep < (100); ++rep) {
    int len = 10000;
    string s(len, '?');
    for (int i = (0); i < (len); ++i) s[i] = '0' + rand() % 10;
    while (((int)(s).size()) > 1 && s[0] == '0') s = s.substr(1);
    BigInt a = parse(s);
    string have = format(a);
    if (have == s) {
      printf(".");
      continue;
    }
    printf("err\n");
    break;
  }
}
void stressgcd() {
  printf("\nstressgcdsmall\n");
  printf("\nstressgcdlarge lehmer\n");
  for (int rep = (0); rep < (100000); ++rep) {
    BigInt a;
    a.d = vector<unsigned int>(300, 0);
    for (int i = (0); i < (((int)(a.d).size())); ++i)
      for (int j = (0); j < (BIGINTBITS); ++j) a.d[i] |= (rand() % 2) << j;
    normalize(a);
    BigInt b;
    b.d = vector<unsigned int>(300, 0);
    for (int i = (0); i < (((int)(b.d).size())); ++i)
      for (int j = (0); j < (BIGINTBITS); ++j) b.d[i] |= (rand() % 2) << j;
    normalize(b);
    BigInt c = lehmergcd(a, b);
    BigInt d = gcd(a, b);
    if (format(c) != format(d)) {
      printf("err\n");
    }
    if (rep % 1000 == 999) printf(".");
  }
}
void stressmillerrabin() {
  std::mt19937 rnd(123);
  for (int rep = (0); rep < (1000); ++rep) {
    BigInt n = rnd() % 1000;
    int nbits = rnd() % 200;
    for (int i = (0); i < (nbits); ++i) n = n << 1;
    n = n + 1;
    if (isprobableprime(n, rnd)) printf("%s is prime\n", format(n).c_str());
  }
}
void test() {
  local = true;
  locrnd = mt19937(21312);
  int np;
  scanf("%d", &np);
  ploc.clear();
  for (int i = (0); i < (np); ++i) {
    string s;
    cin >> s;
    BigInt p = parse(s);
    assert(isprobableprime(p, locrnd));
    ploc.push_back(p);
  }
  sort(ploc.begin(), ploc.end());
  nloc = 1;
  for (int i = (0); i < (((int)(ploc).size())); ++i) nloc = nloc * ploc[i];
  printf("n=%s\n", format(nloc).c_str());
  for (int rep = (0); rep < (100); ++rep) {
    solve(format(nloc));
    assert(ploc == ans);
    printf(".");
  }
}
void stress() {
  local = true;
  int targetbits = 1024;
  locrnd = mt19937(21312);
  for (int rep = (0); rep < (1000); ++rep) {
    nloc = BigInt(1);
    ploc.clear();
    int nprime = locrnd() % (10 - 2 + 1) + 2;
    for (int i = (0); i < (nprime); ++i) {
      int mxpbits = targetbits / (i + 1);
      BigInt p;
      while (true) {
        BigInt x = randbits(locrnd() % (mxpbits - 2) + 1, locrnd);
        p = 4 * x + 3;
        bool have = false;
        for (int j = (0); j < (((int)(ploc).size())); ++j)
          if (ploc[j] == p) have = true;
        if (have) continue;
        if (isprobableprime(p, locrnd)) break;
      }
      nloc = nloc * p;
      ploc.push_back(p);
    }
    sort(ploc.begin(), ploc.end());
    printf("n=%s\n", format(nloc).c_str());
    solve(format(nloc));
    assert(ploc == ans);
  }
}
int main() {
  run();
  return 0;
}