/// matrix
#define MOD 1000000007
struct Matrix{
    int row, col;
    int ar[101][101]; /// Change matrix size here, also change to long long for safety
    Matrix(){} ///Beware if matrix can contain negative numbers in matrix exponentiation problems
    Matrix(int n, int m, int diagonal = 0){
        clr(ar);
        row = n, col = m;
        for (int i = min(n, m) - 1; i >= 0; i--) ar[i][i] = diagonal;
    }
    /// To multiply two matrices A and B, the number of columns in A must equal the number of rows in B
    Matrix operator* (const Matrix& other) const{ /// hash = 709758
        int i, j, k;
        Matrix res(row, other.col);
        long long x, y = (long long)MOD * MOD;
        for(i = 0; i < row; i++){
            for(j = 0; j < other.col; j++){
                for(k = 0, x = 0; k < col; k++){
                    x += ((long long)ar[i][k] * other.ar[k][j]); /// replace matrix other with its transpose matrix to reduce cache miss
                    if (x >= y) x -= y;
                }
                res.ar[i][j] = x % MOD;
            }
        }
        return res;
    }
    Matrix operator^ (long long n) const{
        Matrix x = *this, res = Matrix(row, col, 1);
        while (n){
            if (n & 1) res = res * x;
            n = n >> 1, x = x * x;
        }
        return res;
    }
    /// Transpose matrix, T[i][j] = ar[j][i]
    Matrix transpose(){
        Matrix res = Matrix(col, row);
        for (int i = 0; i < row; i++){
            for (int j = 0; j < col; j++){
                res.ar[j][i] = ar[i][j];
            }
        }
        return res;
    }
    /// rotates the matrix 90 degrees clockwise
    Matrix rotate(){
        Matrix res = this->transpose();
        for (int i = 0; i < res.row; i++) reverse(res.ar[i], res.ar[i] + res.col);
        return res;
    }
    inline void print(){
        for (int i = 0; i < row; i++){
            for (int j = 0; j < col; j++){
                printf("%d%c", ar[i][j], ((j + 1) == col) ? 10 : 32);
            }
        }
    }
};
int main(){
    Matrix a = Matrix(4, 5, 1);
    int k = 0;
    for (int i = 0; i < a.row; i++){
        for (int j = 0; j < a.col; j++){
            a.ar[i][j] = ++k;
        }
    }
    a.print();
    puts("");
    Matrix b = a.rotate();
    b.print();
    return 0;
    Matrix x = Matrix(5, 5, 5);
    Matrix y = x ^ 5;
    x.print();
    y.print();
}


/***

Sometimes we may need to maintain more than one recurrence, where they are interrelated.
For example, let a recurrence relation be:
g(n) = 2g(n-1) + 2g(n-2) + f(n), where, f(n) = 2f(n-1) + 2f(n-2).
Here, recurrence g(n) is dependent upon f(n) and the can be calculated in the same matrix
but of increased dimensions. Lets design the matrices A, B then we'll try to find matrix M.


                        Matrix A                Matrix B

                        |  g(n)  |              | g(n+1) |
                        | g(n-1) |              |  g(n)  |
                        | f(n+1) |              | f(n+2) |
                        |  f(n)  |              | f(n+1) |


Here, g(n+1) = 2g(n) + 2g(n-1) + f(n+1) and f(n+2) = 2f(n+1) + 2f(n).
Now, using the above process, we can generate the objective matrix M as follows:

| 2  2  1  0 |
| 1  0  0  0 |
| 0  0  2  2 |
| 0  0  1  0 |


/// Matrix Rotations:

Rotate by +90:
Transpose
Reverse each row

Rotate by -90:
Transpose
Reverse each column


Rotate by +180:
Method 1: Rotate by +90 twice
Method 2: Reverse each row and then reverse each column

Rotate by -180:
Method 1: Rotate by -90 twice
Method 2: Reverse each column and then reverse each row
Method 3: Reverse by +180 as they are same

***/



/// Lucas theorem to calculate binomial co-efficients modulo a prime
#define MAXP 100010
namespace lc{
    int MOD = 1000000007;
    int fact[MAXP], inv[MAXP];
    /// Call once with the modulo prime
    void init(int prime){
        MOD = prime;
        fact[0] = 1, inv[MOD - 1] = MOD - 1;
        for (int i = 1; i < MOD; i++) fact[i] = ((long long)fact[i - 1] * i) % MOD;
        for (int i = MOD - 2; i >= 0; i--) inv[i] = ((long long)inv[i + 1] * (i + 1)) % MOD;
    }
    inline int count(int n, int k){
        if (k > n) return 0;
        int x = ((long long)inv[n - k] * inv[k]) % MOD;
        return ((long long)x * fact[n]) % MOD;
    }
    /// Lucas theorem, calculates binomial(n, k) modulo MOD, MOD must be a prime
    inline int binomial(long long n, long long k){
        if (k > n) return 0;
        int res = 1;
        k = min(k, n - k);
        while (k && res){
            res = ((long long)res * count(n % MOD, k % MOD)) % MOD;
            n /= MOD, k /= MOD;
        }
        return res;
    }
    /*** Alternate and extended functionalities ***/
    /// Must call init with prime before (Or set lc::MOD = prime)
    /// Computes (n! / (p ^ (n / p))) % p in O(p log(n)) time, p MUST be a prime
    /// That is, calculating n! without p's powers
    /// For instance factmod(9, 3) = (1 * 2 * 4 * 5 * 2 * 7 * 8 * 1) % 3 = 1
    inline int factmod(long long n, int p){
        int i, res = 1;
        while (n > 1) {
            if ((n / p) & 1) res = ((long long)res * (p - 1)) % p;
            for (i = n % p; i > 1; i--) res = ((long long)res * i) % p;
            n /= p;
        }
        return (res % p);
    }
    inline int expo(int a, int b){
        int res = 1;
        while (b){
            if (b & 1) res = (long long)res * a % MOD;
            a = (long long)a * a % MOD;
            b >>= 1;
        }
        return res;
    }
    /// Trailing zeros of n! in base p, p is a prime
    inline long long fact_ctz(long long n, long long p){
        long long x = p, res = 0;
        while (n >= x){
            res += (n / x);
            x *= p;
        }
        return res;
    }
    /// Calculates binomial(n, k) modulo MOD, MOD must be a prime
    inline int binomial2(long long n, long long k){
        if (k > n) return 0;
        if (fact_ctz(n, MOD) != (fact_ctz(k, MOD) + fact_ctz(n - k, MOD))) return 0;
        int a = factmod(n - k, MOD), b = factmod(k, MOD), c = factmod(n, MOD);
        int x = ((long long)expo(a, MOD - 2) * expo(b, MOD - 2)) % MOD;
        return ((long long)x * c) % MOD;
    }
}
int main(){
    lc::init(997);
    printf("%d\n", lc::binomial(10, 5));
    printf("%d\n", lc::binomial(1996, 998));
    lc::MOD = 10007;
    printf("%d\n", lc::binomial2(10, 5));
    printf("%d\n", lc::binomial2(1996, 998));
    return 0;
}


/// maximum divisors
unsigned long long n, res, idx;
int p, primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71};
unsigned long long mul(unsigned long long a, unsigned long long b){
    unsigned long long res = 0;
    while (b){
        if (b & 1LL) res = (res + a);
        if (res > n) return 0;
        a = (a << 1LL);
        b >>= 1LL;
    }
    return res;
}
void backtrack(int i, int lim, unsigned long long val, unsigned long long r){
    if ((r > res) || (r == res && val < idx)) res = r, idx = val;
    if (i == p) return;
    int d;
    unsigned long long x = val;
    for (d = 1; d <= lim; d++){
        x = mul(x, primes[i]);
        if (x == 0) return;
        backtrack(i + 1, d, x, r * (d + 1));
    }
}
int main(){
    /* Tested for n <= 10^18 */
    p = sizeof(primes) / sizeof(int);
    while (scanf("%llu", &n) != EOF){
        res = 0;
        backtrack(0, 100, 1, 1);
        printf("%llu = %llu\n", idx, res);
    }
    return 0;
}



/// Miller Rabin
#define MAX 1000010
namespace prm{ /// hash = 130793
    bitset <MAX> flag;
    long double op = 0.0;
    int p = 0, prime[78777];
    const int base[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    void Sieve(){
        int i, j, x;
        for (i = 3; i < MAX; i += 2) flag[i] = true;
        for (i = 3, flag[2] = true; (i * i) < MAX; i += 2){
            if (flag[i]){
                for (j = (i * i), x = i << 1; j < MAX; j += x){
                    flag[j] = false;
                }
            }
        }
        for (i = 2; i < MAX; i++){
            if (flag[i]) prime[p++] = i;
        }
    }
    void init(){
        if (!flag[2]) Sieve();
    }
    inline long long mul(long long a, long long b, long long MOD){
       if ((MOD < 3037000500LL)) return ((a * b) % MOD);
       long double res = a;
       res *= b;
       long long c = (long long)(res * op);
       a *= b;
       a -= c * MOD;
       if (a >= MOD) a -= MOD;
       if (a < 0) a += MOD;
       return a;
    }
    inline long long expo(long long x, long long n, long long m){
        long long res = 1;
        while (n){
            if (n & 1) res = mul(res, x, m);
            x = mul(x, x, m);
            n >>= 1;
        }
        return (res % m);
    }
    inline bool miller_rabin(long long p){
        if (p < MAX) return flag[p];
        if ((p + 1) & 1) return false;
        for (int i = 1; i < 10; i++){ /// basic iterations
            if (!(p % prime[i])) return false;
        }
        long long a, m, x, s = p - 1, y = p - 1;
        op = (long double)1 / p, s = s >> __builtin_ctzll(s);
        for (int i = 0; i < 7; i++) {
            x = s, a = (base[i] % y) + 1;
            m = expo(a, x, p);
            while ((x != y) && (m != 1) && (m != y)) m = mul(m, m, p), x <<= 1;
            if ((m != y) && !(x & 1)) return false;
        }
        return true;
    }
    inline long long countdiv(long long n){
        int i, j, c;
        long long x, res = 1;
        for (i = 0; i < p; i++){
            x = prime[i];
            if ((x * x * x) > n) break;
            c = 1;
            while (!(n % x)) c++, n /= x;
            res *= c;
        }
        if (miller_rabin(n)) res <<= 1;
        else if (n > 1) {
            x = sqrt((long double)0.95 + n); /// may be change to sqrtl() ?
            if ((x * x) == n && miller_rabin(x)) res *= 3;
            else res <<= 2;
        }
        return res;
    }
}
int main(){
    prm::init();
}



/// mobius function
#define LEN 666666
#define MAX 10000010
int len = 0, prime[LEN];
char mu[MAX] = {0}, flag[MAX] = {0};
/// mu[1] = 1, mu[n] = 0 if n has a squared prime factor,
/// mu[n] = 1 if n is square-free with even number of prime factors
/// mu[n] = -1 if n is square-free with odd number of prime factors
void Mobius(){
    mu[1] = 1;
    int i, j, k;
    for (i = 2; i < MAX; i++){
        if (!flag[i]) mu[i] = -1, prime[len++] = i;
        for (j = 0; j < len && (k = i * prime[j]) < MAX; j++){
            flag[k] = true;
            if (!(i % prime[j])){
                mu[k] = 0;
                break;
            }
            else mu[k] -= mu[i];
        }
    }
}
void Mobius(){ /// Simplified NlogN version
    int i, j;
    mu[1] = 1;
    for (i = 1; i < MAX; i++){
        for (j = i + i; j < MAX; j += i){
            mu[j] -= mu[i];
        }
    }
}
void Mobius(){ /// Simplified version optimized
    int i, j;
    mu[1] = 1;
    for (i = 1; i < MAX; i++){
        if (mu[i]){
            for (j = i + i; j < MAX; j += i){
                mu[j] -= mu[i];
            }
        }
    }
}
int main(){
    Mobius();
}



/// phi
#define MAX 4000010
int phi[MAX];
void Totient(){
    clr(phi);
    int i, j, x;
    for (i = 1; i < MAX; i++){
        phi[i] += i;
        for (j = (i << 1); j < MAX; j += i){
            phi[j] -= phi[i];
        }
    }
}
int main(){
    Totient();
}



/// Pick's Theorem
struct Point{
    long long x, y;
    Point(){}
    Point(long long x, long long y) : x(x), y(y){}
};
/// twice the area of polygon
long long double_area(Point poly[], int n){
    long long res = 0;
    for (int i = 0, j = n - 1; i < n; j = i++){
        res += ((poly[j].x + poly[i].x) * (poly[j].y - poly[i].y));
    }
    return abs(res);
}
/// number of lattice points strictly on polygon border
long long on_border(Point poly[], int n){
    long long res = 0;
    for (int i = 0, j = n - 1; i < n; j = i++){
        res += __gcd(abs(poly[i].x - poly[j].x), abs(poly[i].y - poly[j].y));
    }
    return res;
}
/// number of lattice points strictly inside polygon
long long interior(Point poly[], int n){
    long long res = 2 + double_area(poly, n) - on_border(poly, n);
    return res / 2;
}
int main(){
    Point ar[10];
    ar[0] = Point(0, 0);
    ar[1] = Point(3, 0);
    ar[2] = Point(3, 3);
    ar[3] = Point(0, 3);
    dbg(on_border(ar, 4)); /// 12
    dbg(interior(ar, 4)); /// 4
    return 0;
}



/// Pollard Rho
const long long LIM = LLONG_MAX;
long long mul(long long a, long long b, long long m){
    long long x, res;
    if (a < b) swap(a, b);
    if (!b) return 0;
    if (a < (LIM / b)) return ((a * b) % m);
    res = 0, x = (a % m);
    while (b){
        if (b & 1){
            res = res + x;
            if (res >= m) res -= m;
        }
        b >>= 1;
        x <<= 1;
        if (x >= m) x -= m;
    }
    return res;
}
long long expo(long long x, long long n, long long m){
    long long res = 1;

    while (n){
        if (n & 1) res = mul(res, x, m);
        x = mul(x, x, m);
        n >>= 1;
    }
    return (res % m);
}
const int small_primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 51, 53, 59, 61, 67, 71};
bool miller_rabin(long long p, int lim){
    long long a, s, m, x, y;
    s = p - 1, y = p - 1;
    while (!(s & 1)) s >>= 1;
    while (lim--){
        x = s;
        a = (rand() % y) + 1;
        m = expo(a, x, p);
        while ((x != y) && (m != 1) && (m != y)){
            m = mul(m, m, p);
            x <<= 1;
        }
        if ((m != y) && !(x & 1)) return false;
    }
    return true;
}
void brent_pollard_rho(uint64_t n, vector <uint64_t> &v){
    if (miller_rabin(n, 10)){
        v.push_back(n);
        return;
    }
    uint64_t a, g, x, y;
    y = 1;
    a = rand() % n;
    x = rand() % n;
    for (int i = 0; ((i * i) >> 1) < n; i++){
        x = mul(x, x, n);
        x += a;
        if (x < a) x += (ULLONG_MAX - n) + 1;
        x %= n;
        g = __gcd(n, y - x);
        if ((g != 1) && (g != n)){
            n /= g;
            brent_pollard_rho(g, v);
            if (n != g) brent_pollard_rho(n, v);
            else if (miller_rabin(n, 10)) v.push_back(n);
            return;
        }
        if (!(i & (i - 1))) y = x;
    }
    brent_pollard_rho(n, v);
}
void factorize(uint64_t n, vector <uint64_t> &v){
    srand(time(0));
    int i, j, x;
    for (i = 0; i < 21; i++){
        x = small_primes[i];
        while ((n % x) == 0){
            n /= x;
            v.push_back(x);
        }
    }
    if (n > 1) brent_pollard_rho(n, v);
    sort(v.begin(), v.end());
}
int main(){
    int i, t;
    uint64_t n, x;
    cin >> t;
    while (t--){
        cin >> n;
        vector <uint64_t> v;
        factorize(n, v);
        sort(v.begin(), v.end());
        v.push_back(-1);
        int len = v.size();
        int c = 0, counter = 0;
        printf("%llu = ", n);
        for (i = 0; (i + 1) < len; i++){
            if (v[i] == v[i + 1]) counter++;
            else{
                if (c) printf(" * ");
                if (counter) printf("%llu^%d", v[i], ++counter);
                else printf("%llu", v[i]);
                c++, counter = 0;
            }
        }
        puts("");
    }
    return 0;
}


/// Prime Counting Functions
#define chkbit(ar, i) (((ar[(i) >> 6]) & (1 << (((i) >> 1) & 31))))
#define setbit(ar, i) (((ar[(i) >> 6]) |= (1 << (((i) >> 1) & 31))))
#define isprime(x) (( (x) && ((x)&1) && (!chkbit(ar, (x)))) || ((x) == 2))
namespace pcf{
    ///   Prime-Counting Function
    ///   initialize once by calling init()
    ///   Legendre(m) and Lehmer(m) returns the number of primes less than or equal to m
    #define MAXN 1000010
    #define MAX_PRIMES 1000010
    #define PHI_M 10010
    #define PHI_N 48
    unsigned int ar[(MAXN >> 6) + 5] = {0};
    int len = 0, primes[MAX_PRIMES], counter[MAXN], phi_dp[PHI_N][PHI_M];
    void Sieve(int n, unsigned int* ar, int* primes, int& len){
        n++;
        setbit(ar, 0), setbit(ar, 1);
        int i, j, k, lim = sqrt(n) + 1;
        for (i = 3; i < lim; i++, i++){
            if (!chkbit(ar, i)){
                k = i << 1;
                for (j = (i * i); j < n; j += k) setbit(ar, j);
            }
        }
        for (i = 1; i < n; i++){
            if (isprime(i)) primes[len++] = i;
            counter[i] = len;
        }
    }
    void Sieve(int n){
        Sieve(n, ar, primes, len);
    }
    void init(){
        Sieve(MAXN - 1);
        int m, n, res;
        for (n = 0; n < PHI_N; n++){
            for (m = 0; m < PHI_M; m++){
                if (!n) res = m;
                else res = phi_dp[n - 1][m] - phi_dp[n - 1][m / primes[n - 1]];
                phi_dp[n][m] = res;
            }
        }
    }
    int phi(int m, int n){
        if (m < PHI_M && n < PHI_N) return phi_dp[n][m];
        if (n == 1) return ((++m) >> 1);
        if (primes[n - 1] >= m) return 1;
        return phi(m, n - 1) - phi(m / primes[n - 1], n - 1);
    }
    int Legendre(int m){
        if (m < MAXN) return counter[m];
        int lim = sqrt(m) + 1;
        int n = upper_bound(primes, primes + len, lim) - primes;
        return phi(m, n) + (n - 1);
    }
    int Lehmer(int m){
        if (m < MAXN) return counter[m];
        int i, j, a, b, c, w, lim, res;
        b = sqrt(m), c = Lehmer(cbrt(m)), a = Lehmer(sqrt(b)), b = Lehmer(b);
        res = phi(m, a) + (((b + a - 2) * (b - a + 1)) >> 1);
        for (i = a; i < b; i++){
            w = m / primes[i];
            lim = Lehmer(sqrt(w)), res -= Lehmer(w);
            if (i <= c){
                for (j = i; j < lim; j++){
                    res += j;
                    res -= Lehmer(w / primes[j]);
                }
            }
        }
        return res;
    }
}
int main(){
    pcf::init();
    return 0;
}



/// Segmented Sieve
#define MAX 1000010
#define BASE_SQR 216
#define BASE_LEN 10010
#define BASE_MAX 46656
#define chkbit(ar, i) (((ar[(i) >> 6]) & (1 << (((i) >> 1) & 31))))
#define setbit(ar, i) (((ar[(i) >> 6]) |= (1 << (((i) >> 1) & 31))))
int p, primes[BASE_LEN];
unsigned int base[(BASE_MAX >> 6) + 5], isprime[(MAX >> 6) + 5];
void Sieve(){
    clr(base);
    int i, j, k;
    for (i = 3; i < BASE_SQR; i++, i++){
        if (!chkbit(base, i)){
            k = i << 1;
            for (j = (i * i); j < BASE_MAX; j += k){
                setbit(base, j);
            }
        }
    }
    p = 0;
    for (i = 3; i < BASE_MAX; i++, i++){
        if (!chkbit(base, i)){
            primes[p++] = i;
        }
    }
}
int SegmentedSieve(long long a, long long b){
    long long j, k, x;
    int i, d, counter = 0;
    if (a <= 2 && 2 <= b) counter = 1; /// 2 is counted separately if in range
    if (!(a & 1)) a++;
    if (!(b & 1)) b--;
    if (a > b) return counter;
    clr(isprime);
    for (i = 0; i < p; i++){
        x = primes[i];
        if ((x * x) > b) break;
        k = x << 1;
        j = x * ((a + x - 1) / x);
        if (!(j & 1)) j += x;
        else if (j == x) j += k;
        while (j <= b){
            setbit(isprime, j - a);
            j += k;
        }
    }
    /// Other primes in the range except 2 are added here
    d = (b - a + 1);
    for (i = 0; i < d; i++, i++){
        if (!chkbit(isprime, i) && (a + i) != 1) counter++;
    }
    return counter;
}
int main(){
    Sieve();
    int T = 0, t, i, j, a, b;
    scanf("%d", &t);
    while (t--){
        scanf("%d %d", &a, &b);
        printf("Case %d: %d\n", ++T, SegmentedSieve(a, b));
    }
    return 0;
}



/// simplex
#define MAXC 1010
#define MAXV 1010
#define EPS 1e-13
#define MINIMIZE -1
#define MAXIMIZE +1
#define LESSEQ -1
#define EQUAL 0
#define GREATEQ 1
#define INFEASIBLE -1
#define UNBOUNDED 666
namespace lp{
    long double val[MAXV], ar[MAXC][MAXV];
    int m, n, solution_flag, minmax_flag, basis[MAXC], index[MAXV];
    inline void init(int nvars, long double f[], int flag){
        solution_flag = 0;
        ar[0][nvars] = 0.0;
        m = 0, n = nvars, minmax_flag = flag;
        for (int i = 0; i < n; i++){
            ar[0][i] = f[i] * minmax_flag;
        }
    }
    inline void add_constraint(long double C[], long double lim, int cmp){
        m++, cmp *= -1;
        if (cmp == 0){
            for (int i = 0; i < n; i++) ar[m][i] = C[i];
            ar[m++][n] = lim;
            for (int i = 0; i < n; i++) ar[m][i] = -C[i];
            ar[m][n] = -lim;
        }
        else{
            for (int i = 0; i < n; i++) ar[m][i] = C[i] * cmp;
            ar[m][n] = lim * cmp;
        }
    }
    inline void init(){
        for (int i = 0; i <= m; i++) basis[i] = -i;
        for (int j = 0; j <= n; j++){
            ar[0][j] = -ar[0][j], index[j] = j, val[j] = 0;
        }
    }
    inline void pivot(int m, int n, int a, int b){
        for (int i = 0; i <= m; i++){
            if (i != a){
                for (int j = 0; j <= n; j++){
                    if (j != b){
                        ar[i][j] -= (ar[i][b] * ar[a][j]) / ar[a][b];
                    }
                }
            }
        }
        for (int j = 0; j <= n; j++){
            if (j != b) ar[a][j] /= ar[a][b];
        }
        for (int i = 0; i <= m; i++){
            if (i != a) ar[i][b] = -ar[i][b] / ar[a][b];
        }
        ar[a][b] = 1.0 / ar[a][b];
        swap(basis[a], index[b]);
    }
    inline long double solve(){
        init();
        int i, j, k, l;
        for (; ;){
            for (i = 1, k = 1; i <= m; i++){
                if ((ar[i][n] < ar[k][n]) || (ar[i][n] == ar[k][n] && basis[i] < basis[k] && (rand() & 1))) k = i;
            }
            if (ar[k][n] >= -EPS) break;

            for (j = 0, l = 0; j < n; j++){
                if ((ar[k][j] < (ar[k][l] - EPS)) || (ar[k][j] < (ar[k][l] - EPS) && index[i] < index[j] && (rand() & 1))){
                    l = j;
                }
            }
            if (ar[k][l] >= -EPS){
                solution_flag = INFEASIBLE;
                return -1.0;
            }
            pivot(m, n, k, l);
        }
        for (; ;){
            for (j = 0, l = 0; j < n; j++){
                if ((ar[0][j] < ar[0][l]) || (ar[0][j] == ar[0][l] && index[j] < index[l] && (rand() & 1))) l = j;
            }
            if (ar[0][l] > -EPS) break;
            for (i = 1, k = 0; i <= m; i++){
                if (ar[i][l] > EPS && (!k || ar[i][n] / ar[i][l] < ar[k][n] / ar[k][l] - EPS || (ar[i][n] / ar[i][l] < ar[k][n] / ar[k][l] + EPS && basis[i] < basis[k]))){
                    k = i;
                }
            }
            if (ar[k][l] <= EPS){
                solution_flag = UNBOUNDED;
                return -666.0;
            }
            pivot(m, n, k, l);
        }
        for (i = 1; i <= m; i++){
            if (basis[i] >= 0) val[basis[i]] = ar[i][n];
        }
        solution_flag = 1;
        return (ar[0][n] * minmax_flag);
    }
}


/// Thomas algorithm to solve tri-digonal system of equations in O(n)
/// Equation of the form: (x_prev * l) + (x_cur * p) + (x_next * r) = rhs
struct equation{
    long double l, p, r, rhs;
    equation(){}
    equation(long double l, long double p, long double r, long double rhs = 0.0):
        l(l), p(p), r(r), rhs(rhs){}
};
vector <long double> thomas_algorithm(int n, vector <struct equation> ar){
    ar[0].r = ar[0].r / ar[0].p;
    ar[0].rhs = ar[0].rhs / ar[0].p;
    for (int i = 1; i < n; i++){
        long double v = 1.0 / (ar[i].p - ar[i].l * ar[i - 1].r);
        ar[i].r = ar[i].r * v;
        ar[i].rhs = (ar[i].rhs - ar[i].l * ar[i - 1].rhs) * v;
    }
    for (int i = n - 2; i >= 0; i--) ar[i].rhs = ar[i].rhs - ar[i].r * ar[i + 1].rhs;
    vector <long double> res;
    for (int i = 0; i < n; i++) res.push_back(ar[i].rhs);
    return res;
}



/// Karatsuba
#define MAX 131072 /// Must be a power of 2
#define MOD 1000000007
unsigned long long temp[128];
int ptr = 0, buffer[MAX * 6];
/// n is a power of 2
void karatsuba(int n, int *a, int *b, int *res){ /// hash = 829512
    int i, j, h;
    if (n < 17){ /// Reduce recursive calls by setting a threshold
        for (i = 0; i < (n + n); i++) temp[i] = 0;
        for (i = 0; i < n; i++){
            if (a[i]){
                for (j = 0; j < n; j++){
                    temp[i + j] += ((long long)a[i] * b[j]);
                }
            }
        }
        for (i = 0; i < (n + n); i++) res[i] = temp[i] % MOD;
        return;
    }
    h = n >> 1;
    karatsuba(h, a, b, res);
    karatsuba(h, a + h, b + h, res + n);
    int *x = buffer + ptr, *y = buffer + ptr + h, *z = buffer + ptr + h + h;

    ptr += (h + h + n);
    for (i = 0; i < h; i++){
        x[i] = a[i] + a[i + h], y[i] = b[i] + b[i + h];
        if (x[i] >= MOD) x[i] -= MOD;
        if (y[i] >= MOD) y[i] -= MOD;
    }
    karatsuba(h, x, y, z);
    for (i = 0; i < n; i++) z[i] -= (res[i] + res[i + n]);
    for (i = 0; i < n; i++){
        res[i + h] = (res[i + h] + z[i]) % MOD;
        if (res[i + h] < 0) res[i + h] += MOD;
    }
    ptr -= (h + h + n);
}
/// multiplies two polynomial a(degree n) and b(degree m) and returns the result modulo MOD in a
/// returns the degree of the multiplied polynomial
/// note that a and b are changed in the process
int mul(int n, int *a, int m, int *b){ /// hash = 903808
    int i, r, c = (n < m ? n : m), d = (n > m ? n : m), *res = buffer + ptr;
    r = 1 << (32 - __builtin_clz(d) - (__builtin_popcount(d) == 1));
    for (i = d; i < r; i++) a[i] = b[i] = 0;
    for (i = c; i < d && n < m; i++) a[i] = 0;
    for (i = c; i < d && m < n; i++) b[i] = 0;

    ptr += (r << 1), karatsuba(r, a, b, res), ptr -= (r << 1);
    for (i = 0; i < (r << 1); i++) a[i] = res[i];
    return (n + m - 1);
}
int a[MAX * 2], b[MAX * 2];
int main(){
    int i, j, k, n = MAX - 10;
    for (i = 0; i < n; i++) a[i] = ran(1, 1000000000);
    for (i = 0; i < n; i++) b[i] = ran(1, 991929183);
    clock_t start = clock();
    mul(n, a, n, b);
    dbg(a[n / 2]);
    for (i = 0; i < (n << 1); i++){
        if (a[i] < 0) puts("YO");
    }
    printf("%0.5f\n", (clock() - start) / (1.0 * CLOCKS_PER_SEC));
    return 0;
}


/// Integral Determinant
/// Finds the determinant of a square matrix
/// Returns 0 if the matrix is singular or degenerate (hence no determinant exists)
/// Absolute value of final answer should be < MOD / 2
#define MAX 1010
const long long MOD = 4517409488245517117LL;
const long double OP = (long double)1 / 4517409488245517117LL;
long long mul(long long a, long long b){
   long double res = a;
   res *= b;
   long long c = (long long)(res * OP);
   a *= b;
   a -= c * MOD;
   if (a >= MOD) a -= MOD;
   if (a < 0) a += MOD;
   return a;
}
long long expo(long long x, long long n){
    long long res = 1;
    while (n){
        if (n & 1) res = mul(res, x);
        x = mul(x, x);
        n >>= 1;
    }
    return res;
}
int gauss(int n, long long ar[MAX][MAX]){
    long long x, y;
    int i, j, k, l, p, counter = 0;
    for (i = 0; i < n; i++){
        for (p = i, j = i + 1; j < n && !ar[p][i]; j++){
            p = j;
        }
        if (!ar[p][i]) return -1;
        for (j = i; j < n; j++){
            x = ar[p][j], ar[p][j] = ar[i][j], ar[i][j] = x;
        }
        if (p != i) counter++;
        for (j = i + 1; j < n; j++){
            x = expo(ar[i][i], MOD - 2);
            x = mul(x, MOD - ar[j][i]);
            for (k = i; k < n; k++){
                ar[j][k] = ar[j][k] + mul(x, ar[i][k]);
                if (ar[j][k] >= MOD) ar[j][k] -= MOD;
            }
        }
    }
    return counter;
}
long long determinant(int n, long long ar[MAX][MAX]){
    int i, j, free;
    long long res = 1;
    for (i = 0; i < n; i++){
        for (j = 0; j < n; j++){
            if (ar[i][j] < 0) ar[i][j] += MOD;
        }
    }
    free = gauss(n, ar);
    if (free == -1) return 0; /// Determinant is 0 so matrix is not invertible, singular or degenerate matrix
    for (i = 0; i < n; i++) res = mul(res, ar[i][i]);
    if (free & 1) res = MOD - res;
    if ((MOD - res) < res) res -= MOD; /// Determinant can be negative so if determinant is more close to MOD than 0, make it negative
    return res;
}
int n;
long long ar[MAX][MAX];
int main(){
    int t, i, j, k, l;
    while (scanf("%d", &n) != EOF){
        if (n == 0) break;
        for (i = 0; i < n; i++){
            for (j = 0; j < n; j++){
                scanf("%lld", &ar[i][j]);
            }
        }
        printf("%lld\n", determinant(n, ar));
    }
    return 0;
}



/// Gaussian Elimination in Modular Field
#define MAXROW 1010
#define MAXCOL 1010
int expo(int a, int b, int MOD){
    int res = 1;
    while (b){
        if (b & 1) res = (long long)res * a % MOD;
        a = (long long)a * a % MOD;
        b >>= 1;
    }
    return res;
}
/// Gaussian elimination in field MOD (MOD should be a prime)
int gauss(int n, int m, int MOD, int ar[MAXROW][MAXCOL], vector<int>& res){
    res.assign(m, 0);
    vector <int> pos(m, -1);
    int i, j, k, l, p, d, free_var = 0;
    const long long MODSQ = (long long)MOD * MOD;
    for (j = 0, i = 0; j < m && i < n; j++){
        for (k = i, p = i; k < n; k++){
            if (ar[k][j] > ar[p][j]) p = k;
        }
        if (ar[p][j]){
            pos[j] = i;
            for (l = j; l <= m; l++) swap(ar[p][l], ar[i][l]);
            d = expo(ar[i][j], MOD - 2, MOD);
            for (k = 0; k < n && d; k++){
                if (k != i && ar[k][j]){
                    int x = ((long long)ar[k][j] * d) % MOD;
                    for (l = j; l <= m && x; l++){
                        if (ar[i][l]) ar[k][l] = (MODSQ + ar[k][l] - ((long long)ar[i][l] * x)) % MOD;
                    }
                }
            }
            i++;
        }
    }
    for (i = 0; i < m; i++){
        if (pos[i] == -1) free_var++;
        else res[i] = ((long long)ar[pos[i]][m] * expo(ar[pos[i]][i], MOD - 2, MOD)) % MOD;
    }
    for (i = 0; i < n; i++) {
        long long val = 0;
        for (j = 0; j < m; j++) val = (val + ((long long)res[j] * ar[i][j])) % MOD;
        if (val != ar[i][m]) return -1;
    }
    return free_var;
}



/// Gaussian Elimination Extended
#define EPS 1e-9
#define MAXROW 512
#define MAXCOL 512

/***

Gauss-Jordan Elimination

n = number of linear equations
m = number of variables
ar[i][m] = right-hand side value of constants

For instance, the system of linear equations becomes:

2x + y -z = 8      ----->  (i)
-3x -y + 2z = -11  ----->  (ii)
-2x + y + 2z = -3  ----->  (iii)

n = 3 (x, y, z), m = 3 (i, ii, iii)
ar[0] = {2, 1, -1, 8}    ----->  (i)
ar[1] = {-3, -1, 2, -11} ----->  (ii)
ar[2] = {-2, 1, 2, -3}   ----->  (iii)


Returns -1 when there is no solution
Otherwise returns the number of independent variables (0 for an unique solution)
Contains a solution in the vector res on successful completion
Note that the array is modified in the process

Notes:
For solving problems on graphs with probability/expectation, make sure the graph
is connected and a single component. If not, then re-number the vertex and solve
for each connected component separately.

***/
int gauss(int n, int m, double ar[MAXROW][MAXCOL], vector<double>& res){ /// hash = 835176
    res.assign(m, 0);
    vector <int> pos(m, -1);
    int i, j, k, l, p, free_var = 0;
    for (j = 0, i = 0; j < m && i < n; j++){
        for (k = i, p = i; k < n; k++){
            if (abs(ar[k][j]) > abs(ar[p][j])) p = k;
        }
        if (abs(ar[p][j]) > EPS){
            pos[j] = i;
            for (l = j; l <= m; l++) swap(ar[p][l], ar[i][l]);
            for (k = 0; k < n; k++){
                if (k != i){
                    double x = ar[k][j] / ar[i][j];
                    for (l = j; l <= m; l++) ar[k][l] -= (ar[i][l] * x);
                }
            }
            i++;
        }
    }
    for (i = 0; i < m; i++){
        if (pos[i] == -1) free_var++;
        else res[i] = ar[pos[i]][m] / ar[pos[i]][i];
    }
    for (i = 0; i < n; i++) {
        double val = 0.0;
        for (j = 0; j < m; j++) val += (res[j] * ar[i][j]);
        if (abs(val - ar[i][m]) > EPS) return -1;
    }
    return free_var;
}



/// FFT extended
#define MAXN 1048576 /// 2 * MAX at least
/// Change long double to double if not required
namespace fft{
    int len, last = -1, step = 0, rev[MAXN];
    long long C[MAXN], D[MAXN], P[MAXN], Q[MAXN];
    struct complx{
        long double real, img;
        inline complx(){
            real = img = 0.0;
        }
        inline complx conjugate(){
            return complx(real, -img);
        }
        inline complx(long double x){
            real = x, img = 0.0;
        }
        inline complx(long double x, long double y){
            real = x, img = y;
        }
        inline complx operator + (complx other){
            return complx(real + other.real, img + other.img);
        }
        inline complx operator - (complx other){
            return complx(real - other.real, img - other.img);
        }
        inline complx operator * (complx other){
            return complx((real * other.real) - (img * other.img), (real * other.img) + (img * other.real));
        }
    } u[MAXN], v[MAXN], f[MAXN], g[MAXN], dp[MAXN], inv[MAXN];
    /// Pre-process roots, inverse roots and fft leaf index
    void build(int& a, long long* A, int& b, long long* B){
        while (a > 1 && A[a - 1] == 0) a--;
        while (b > 1 && B[b - 1] == 0) b--;
        len = 1 << (32 - __builtin_clz(a + b) - (__builtin_popcount(a + b) == 1));
        for (int i = a; i < len; i++) A[i] = 0;
        for (int i = b; i < len; i++) B[i] = 0;
        if (!step++){
            dp[1] = inv[1] = complx(1);
            for (int i = 1; (1 << i) < MAXN; i++){
                double theta = (2.0 * acos(0.0)) / (1 << i);
                complx mul = complx(cos(theta), sin(theta));
                complx inv_mul = complx(cos(-theta), sin(-theta));

                int lim = 1 << i;
                for (int j = lim >> 1; j < lim; j++){
                    dp[2 * j] = dp[j], inv[2 * j] = inv[j];
                    inv[2 * j + 1] = inv[j] * inv_mul;
                    dp[2 * j + 1] = dp[j] * mul;
                }
            }
        }
        if (last != len){
            last = len;
            int bit = (32 - __builtin_clz(len) - (__builtin_popcount(len) == 1));
            for (int i = 0; i < len; i++) rev[i] = (rev[i >> 1] >> 1) + ((i & 1) << (bit - 1));
        }
    }
    /// Fast Fourier Transformation, iterative divide and conquer
    void transform(complx *in, complx *out, complx* ar){
        for (int i = 0; i < len; i++) out[i] = in[rev[i]];
        for (int k = 1; k < len; k <<= 1){
            for (int i = 0; i < len; i += (k << 1)){
                for (int j = 0; j < k; j++){
                    complx z = out[i + j + k] * ar[j + k];
                    out[i + j + k] = out[i + j] - z;
                    out[i + j] = out[i + j] + z;
                }
            }
        }
    }
    /// Fast Fourier Transformation, iterative divide and conquer unrolled and optimized
    void transform_unrolled(complx *in, complx *out, complx* ar){
        for (int i = 0; i < len; i++) out[i] = in[rev[i]];
        for (int k = 1; k < len; k <<= 1){
            for (int i = 0; i < len; i += (k << 1)){
                complx z, *a = out + i, *b = out + i + k, *c = ar + k;
                if (k == 1){
                    z = (*b) * (*c);
                    *b = *a - z, *a = *a + z;
                }
                for (int j = 0; j < k && k > 1; j += 2, a++, b++, c++){
                    z = (*b) * (*c);
                    *b = *a - z, *a = *a + z;
                    a++, b++, c++;
                    z = (*b) * (*c);
                    *b = *a - z, *a = *a + z;
                }
            }
        }
    }
    bool equals(int a, long long* A, int b, long long* B){
        if (a != b) return false;
        for (a = 0; a < b && A[a] == B[a]; a++){}
        return (a == b);
    }
    /// Square of a polynomial
    int square(int a, long long* A){
        build(a, A, a, A);
        for (int i = 0; i < len; i++) u[i] = complx(A[i], 0);
        transform_unrolled(u, f, dp);
        for (int i = 0; i < len; i++) u[i] = f[i] * f[i];
        transform_unrolled(u, f, inv);
        for (int i = 0; i < len; i++) A[i] = (f[i].real / (long double)len) + 0.5;
        return a + a - 1;
    }
    /// Multiplies two polynomials A and B and return the coefficients of their product in A
    /// Function returns degree of the polynomial A * B
    int multiply(int a, long long* A, int b, long long* B){
        if (equals(a, A, b, B)) return square(a, A); /// Optimization
        build(a, A, b, B);
        for (int i = 0; i < len; i++) u[i] = complx(A[i], B[i]);
        transform_unrolled(u, f, dp);
        for (int i = 0; i < len; i++){
            int j = (len - 1) & (len - i);
            u[i] = (f[j] * f[j] - f[i].conjugate() * f[i].conjugate()) * complx(0, -0.25 / len);
        }
        transform_unrolled(u, f, dp);
        for (int i = 0; i < len; i++) A[i] = f[i].real + 0.5;
        return a + b - 1;
    }
    /// Modular multiplication
    int mod_multiply(int a, long long* A, int b, long long* B, int mod){
        build(a, A, b, B);
        int flag = equals(a, A, b, B);
        for (int i = 0; i < len; i++) A[i] %= mod, B[i] %= mod;
        for (int i = 0; i < len; i++) u[i] = complx(A[i] & 32767, A[i] >> 15);
        for (int i = 0; i < len; i++) v[i] = complx(B[i] & 32767, B[i] >> 15);
        transform_unrolled(u, f, dp);
        for (int i = 0; i < len; i++) g[i] = f[i];
        if (!flag) transform_unrolled(v, g, dp);
        for (int i = 0; i < len; i++){
            int j = (len - 1) & (len - i);
            complx c1 = f[j].conjugate(), c2 = g[j].conjugate();
            complx a1 = (f[i] + c1) * complx(0.5, 0);
            complx a2 = (f[i] - c1) * complx(0, -0.5);
            complx b1 = (g[i] + c2) * complx(0.5 / len, 0);
            complx b2 = (g[i] - c2) * complx(0, -0.5 / len);
            v[j] = a1 * b2 + a2 * b1;
            u[j] = a1 * b1 + a2 * b2 * complx(0, 1);
        }
        transform_unrolled(u, f, dp);
        transform_unrolled(v, g, dp);
        long long x, y, z;
        for (int i = 0; i < len; i++){
            x = f[i].real + 0.5, y = g[i].real + 0.5, z = f[i].img + 0.5;
            A[i] = (x + ((y % mod) << 15) + ((z % mod) << 30)) % mod;
        }
        return a + b - 1;
    }
    /// Multiplies two polynomials where intermediate and final values fits in long long
    int long_multiply(int a, long long* A, int b, long long* B){
        int mod1 = 1.5e9;
        int mod2 = mod1 + 1;
        for (int i = 0; i < a; i++) C[i] = A[i];
        for (int i = 0; i < b; i++) D[i] = B[i];
        mod_multiply(a, A, b, B, mod1);
        mod_multiply(a, C, b, D, mod2);
        for (int i = 0; i < len; i++){
            A[i] = A[i] + (C[i] - A[i] + (long long)mod2) * (long long)mod1 % mod2 * mod1;
        }
        return a + b - 1;
    }
    int build_convolution(int n, long long* A, long long* B){
        int i, m, d = 0;
        for (i = 0; i < n; i++) Q[i] = Q[i + n] = B[i];
        for (i = 0; i < n; i++) P[i] = A[i], P[i + n] = 0;
        n *= 2, m = 1 << (32 - __builtin_clz(n) - (__builtin_popcount(n) == 1));
        for (i = n; i < m; i++) P[i] = Q[i] = 0;
        return n;
    }
    /***
        Computes the circular convolution of A and B, denoted A * B, in C
        A and B must be of equal size, if not normalize before calling function
        Example to demonstrate convolution for n = 5:

        c0 = a0b0 + a1b4 + a2b3 + a3b2 + a4b1
        c1 = a0b1 + a1b0 + a2b4 + a3b3 + a4b2
        ...
        c4 = a0b4 + a1b3 + a2b2 + a3b1 + a4b0


        Note: If linear convolution is required, pad with zeros appropriately, as in multiplication

    ***/
    /// Returns the convolution of A and B in A
    void convolution(int n, long long* A, long long* B){
        int len = build_convolution(n, A, B);
        multiply(len, P, len, Q);
        for (int i = 0; i < n; i++) A[i] = P[i + n];
    }
    /// Modular convolution
    void mod_convolution(int n, long long* A, long long* B, int mod){
        int len = build_convolution(n, A, B);
        mod_multiply(len, P, len, Q, mod);
        for (int i = 0; i < n; i++) A[i] = P[i + n];
    }
    /// Convolution in long long
    void long_convolution(int n, long long* A, long long* B){
        int len = build_convolution(n, A, B);
        long_multiply(len, P, len, Q);
        for (int i = 0; i < n; i++) A[i] = P[i + n];
    }
    /// Hamming distance vector of B with every substring of length |pattern| in str
    /// str and pattern consists of only '1' and '0'
    /// str = "01111000010011111111110010001101000100011110101111"
    /// pattern = "1001101001101110101101000"
    /// Sum of values in hamming distance vector = 321
    vector <int> hamming_distance(const char* str, const char* pattern){
        int n = strlen(str), m = strlen(pattern);
        for (int i = 0; i < n; i++) P[i] = Q[i] = 0;
        for (int i = 0; i < n; i++) P[i] = str[i] == '1' ? 1 : -1;
        for (int i = 0, j = m - 1; j >= 0; i++, j--) Q[i] = pattern[j] == '1' ? 1 : -1;
        vector <int> res;
        fft::multiply(n, P, m, Q);
        for (int i = 0; (i + m) <= n; i++){
            res.push_back(m - ((P[i + m - 1] + m) >> 1));
        }
        return res;
    }
}



/// Fast Integer Cube and Square Root
unsigned int fast_sqrt(unsigned int n){
    unsigned int c, g;
    c = g = 0x8000;
    for (; ;){
        if ((g * g) > n) g ^= c;
        c >>= 1;
        if (!c) return g;
        g |= c;
    }
}
int fast_cbrt(int n){
    int x, r = 30, res = 0;
    for (; r >= 0; r -= 3){
        res <<= 1;
        x = (3 * res * (res + 1)) + 1;
        if ((n >> r) >= x){
            res++;
            n -= (x << r);
        }
    }
    return res;
}
unsigned long long fast_sqrt(unsigned long long n){
    unsigned long long c, g;
    c = g = 0x80000000;
    for (; ;){
        if ((g * g) > n) g ^= c;
        c >>= 1;
        if (!c) return g;
        g |= c;
    }
}
unsigned long long fast_cbrt(unsigned long long n){
    int r = 63;
    unsigned long long x, res = 0;
    for (; r >= 0; r -= 3){
        res <<= 1;
        x = (res * (res + 1) * 3) + 1;
        if ((n >> r) >= x){
            res++;
            n -= (x << r);
        }
    }
    return res;
}



/// Extended Euclid
/// Bezout's identity, ax + by = gcd(a,b)
int extended_gcd(int a, int b, int& x, int& y){
    if (!b){
        y = 0, x = 1;
        return a;
    }
    int g = extended_gcd(b, a % b, y, x);
    y -= ((a / b) * x);
    return g;
}
/// Linear diophantine equation, ax + by = c
void diophantine(int a, int b, int c, int& x, int& y){
    int g = extended_gcd(a, b, x, y);
    assert((c % g) == 0); /// c must be a multiply of g
    c /= g;
    x *= c, y *= c;
}



/// Eulerian Numbers
#define MAX 5010
#define MOD 1000000007
/***
Eulerian number A(n,k) is the number of permutations of 1 to n in which exactly k elements are greater than their previous element
Eulerian triangle for n = 1 to 7 and k = 0 to n - 1 below

1
1 1
1 4 1
1 11 11 1
1 26 66 26 1
1 57 302 302 57 1
1 120 1191 2416 1191 120 1

***/
int dp[MAX][MAX];
void generate(){
    int n, k;
    for (n = 0; n < MAX; n++){
        for (k = 1, dp[n][0] = 1; k <= n; k++){
            dp[n][k] = ((long long)dp[n - 1][k] * (k + 1) + (long long)dp[n - 1][k - 1] * (n - k)) % MOD;
        }
    }
}
int main(){
    int n, k;
    generate();
    for (n = 1; n <= 7; n++){
        for (k = 0; k < n; k++){
            printf("%d ", dp[n][k]);
        }
        puts("");
    }
    return 0;
}



/// Discrete Log (General)
int extended_gcd(int a, int b, int& x, int& y){
    /// Bezout's identity, ax + by = gcd(a,b)
    if (!b){
        y = 0, x = 1;
        return a;
    }
    int g = extended_gcd(b, a % b, y, x);
    y -= ((a / b) * x);
    return g;
}
int discrete_log(int g, int h, int p){ /// hash = 167626
    /***
        * returns smallest x such that (g^x) % p = h, -1 if none exists
        * function returns x, the discrete log of h with respect to g modulo p
    ***/
    if (h >= p) return -1;
    if ((g % p) == 0){
        if (h == 1) return 0; /// return -1 if strictly positive integer solution is required
        else return -1;
    }
    int i, c, x, y, z, r, m, counter = 0;
    long long v = 1, d = 1, mul = 1, temp = 1 % p;
    for (int i = 0; i < 100; i++){
        if (temp == h) return i;
        temp = (temp * g) % p;
    }
    while ((v = __gcd(g, p)) > 1){
        if (h % v) return -1;
        h /= v, p /= v;
        d = (d * (g / v)) % p;
        counter++;
    }
    m = ceil(sqrt(p)); /// may be change to sqrtl() ?
    tr1::unordered_map <int, int> mp;
    for (i = 0; i < m; i++){
        if (!mp[mul]) mp[mul] = i + 1;
        mul = (mul * g) % p;
    }
    for (i = 0; i < m; i++){
        z = extended_gcd(d, p, x, y);
        c = p / z;
        r = ((((long long)x * h) / z) % p + p) % p;
        if (mp[r]) return ((i * m) + mp[r] + counter - 1);
        d = (d * mul) % p;
    }
    return -1;
}
int main(){
    int g, h, p, res;
    for (; ;){
        scanf("%d %d %d", &g, &p, &h);
        if (!g && !p && !h) break;
        res = discrete_log(g, h % p, p);
        if (res == -1) puts("No Solution");
        else printf("%d\n", res);
    }
    return 0;
}


/// Discrete Log
int expo(long long x, int n, int m){
    long long res = 1;

    while (n){
        if (n & 1) res = (res * x) % m;
        x = (x * x) % m;
        n >>= 1;
    }
    return (res % m);
}
int extended_gcd(int a, int b, int& x, int& y){
    /// Bezout's identity, ax + by = gcd(a,b)
    if (!b){
        y = 0, x = 1;
        return a;
    }
    int g = extended_gcd(b, a % b, y, x);
    y -= ((a / b) * x);
    return g;
}
int inverse_modulo(int a, int m){
    /// inverse exists if and only if a and m are co-prime
    int x, y, inv;
    extended_gcd(a, m, x, y);
    inv = (x + m) % m;
    return inv;
}
int discrete_log(int g, int h, int p){
    /***
        * returns smallest x such that (g^x) % p = h, -1 if none exists
        * p must be a PRIME
        * function returns x, the discrete log of h with respect to g modulo p
    ***/
    if (h >= p) return -1;
    if ((g % p) == 0){
        if (h == 1) return 0; /// return -1 if strictly positive integer solution is required
        else return -1;
    }
    unordered_map <int, int> mp;
    int i, q, r, m = ceil(sqrt(p)); /// may be change to sqrtl() ?
    long long d = 1, inv = expo(inverse_modulo(g, p), m, p);
    for (i = 0; i <= m; i++){
        if (!mp[d]) mp[d] = i + 1;
        d *= g;
        if (d >= p) d %= p;
    }
    d = h;
    for (q = 0; q <= m; q++){
        r = mp[d];
        if (r) return ((m * q) + (--r));
        d *= inv;
        if (d >= p) d %= p;
    }
    return -1;
}
int main(){
    int T = 0, t, g, h, p;
    scanf("%d", &t);
    while (t--){
        scanf("%d %d %d", &g, &h, &p);
        int x = discrete_log(g, h, p);
        printf("Case %d: %d\n", ++T, x);
    }
    return 0;
}



/// Digits of Factorial
const double A = 4.0 * acos(0.0);
const double B = log10(exp(1.0));
long long digfact(long long n){
    if (n == 0 || n == 1) return 1;
    double x = ((0.5 * log(A * n)) + (n * log(n)) - n) * B;
    return ceil(x);
}
int main(){
    int t;
    long long n;
    scanf("%d", &t);
    while (t--){
        scanf("%lld", &n);
        printf("%lld\n", digfact(n));
    }
    return 0;
}



/// Chinese Remainder Theorem
#define dbg(x) cout << #x << " = " << x << endl
using namespace std;
long long extended_gcd(long long a, long long b, long long& x, long long& y){
    /// Bezout's identity, ax + by = gcd(a,b)
    if (!b){
        y = 0, x = 1;
        return a;
    }
    long long g = extended_gcd(b, a % b, y, x);
    y -= ((a / b) * x);
    return g;
}
long long mod_inverse(long long a, long long m){
    /// inverse exists if and only if a and m are co-prime
    long long x, y, inv;
    extended_gcd(a, m, x, y);
    inv = (x + m) % m;
    return inv;
}
long long CRT(int n, long long* ar, long long* mods){
    /// finds the unique solution x modulo M (product of mods) for which x % mods[i] = ar[i]
    /// mods must be pairwise co-prime
    int i, j;
    long long x, y, res = 0, M = 1;
    for (i = 0; i < n; i++) M *= mods[i];
    for (i = 0; i < n; i++){
        x = M / mods[i];
        y = mod_inverse(x, mods[i]);
        res = (res + (((x * ar[i]) % M) * y)) % M;
    }
    return res;
}
int main(){
    long long mods[] = {3, 5, 7};
    long long ar[] = {2, 3, 2};
    long long res = CRT(3, ar, mods);
    dbg(res);
}



/// Binomial Coefficients Modulo Prime Powers
#define MAXP 10000010
#define ran(a, b) ((((rand() << 15) ^ rand()) % ((b) - (a) + 1)) + (a))
using namespace std;
namespace crt{
    long long extended_gcd(long long a, long long b, long long& x, long long& y){
        if (!b){
            y = 0, x = 1;
            return a;
        }

        long long g = extended_gcd(b, a % b, y, x);
        y -= ((a / b) * x);
        return g;
    }
    long long mod_inverse(long long a, long long m){
        long long x, y, inv;
        extended_gcd(a, m, x, y);
        inv = (x + m) % m;
        return inv;
    }
    long long chinese_remainder(vector <long long> ar, vector <long long> mods){
        int i, j;
        long long x, y, res = 0, M = 1;
        for (i = 0; i < ar.size(); i++) M *= mods[i];
        for (i = 0; i < ar.size(); i++){
            x = M / mods[i];
            y = mod_inverse(x, mods[i]);
            res = (res + (((x * ar[i]) % M) * y)) % M;
        }
        return res;
    }
}
namespace bin{
    int dp[MAXP];
    long long mod = 0;
    long long trailing(long long x, long long p){
        long long res = 0;
        while (x){
            x /= p;
            res += x;
        }
        return res;
    }
    long long expo(long long x, long long n, long long m){
        if (!n) return 1;
        else if (n & 1) return ((expo(x, n - 1, m) * x) % m);
        else{
            long long r = expo(x, n >> 1, m);
            return ((r * r) % m);
        }
    }
    long long factorial(long long x, long long p){
        long long res = expo(dp[mod - 1], x / mod, mod);
        if (x >= p) res = res * factorial(x / p, p) % mod;
        return res * dp[x % mod] % mod;
    }
    /// binomial co-efficients modulo p^q (p must be a prime)
    long long binomial(long long n, long long k, long long p, long long q){
        if (k > n) return 0;
        if (n == k || k == 0) return 1;
        int i, j;
        for (i = 0, mod = 1; i < q; i++) mod *= p;
        long long t = trailing(n, p) - trailing(k, p) - trailing(n - k, p);
        if (t >= q) return 0;
        assert(mod < MAXP);
        for (dp[0] = 1, i = 1; i < mod; i++){
            dp[i] = (long long)dp[i - 1] * (i % p ? i : 1) % mod;
        }
        long long res = factorial(n, p) * expo(factorial(k, p) * factorial(n - k, p) % mod, (mod / p) * (p - 1) - 1, mod) % mod;
        while (t--) res = res * p % mod;
        return res;
    }
    /// binomial co-efficients modulo m (p_i^q_i of m must be less than MAXP)
    long long binomial(long long n, long long k, long long m){
        if (k > n || m == 1) return 0;
        if (n == k || k == 0) return 1;
        vector < pair <int, int > > factors;
        for (long long i = 2; i * i <= m; i++){
            int c = 0;
            while (m % i == 0){
                c++;
                m /= i;
            }
            if (c) factors.push_back(make_pair(i, c));
        }
        if (m > 1) factors.push_back(make_pair(m, 1));
        vector <long long> ar, mods;
        for (int i = 0; i < factors.size(); i++){
            long long x = 1;
            for (int j = 0; j < factors[i].second; j++) x *= factors[i].first;
            mods.push_back(x), ar.push_back(binomial(n, k, factors[i].first, factors[i].second));
        }
        return crt::chinese_remainder(ar, mods);
    }
}



///All Divisors in Range
#define MAX 1000010
short len[MAX];
int L[MAX], *divisors[MAX];
void Generate(){
    int i, j, k, c, d, x;
    len[0] = len[1] = L[0] = L[1] = 1;
    for (i = 4; i < MAX; i++, i++) len[i] = 2;
    for (i = 3; (i * i) < MAX; i += 2){
        if (!len[i]){
            for (j = (i * i), d = i << 1; j < MAX; j += d){
                if (!len[j]) len[j] = i;
            }
        }
    }
    for (i = 2; i < MAX; i++){
        if (!len[i]) L[i] = i;
        else{
            L[i] = len[i];
            x = L[i /len[i]];
            if (x > L[i]) L[i] = x;
        }
    }
    divisors[1] = (int *) malloc(sizeof(int));
    divisors[1][0] = 1, len[1] = 1;
    for (i = 2; i < MAX; i++){
        c = 0, k = i;
        while (k > 1 && L[k] == L[i]){
            c++;
            k /= L[k];
        }
        len[i] = (c + 1) * len[k];
        divisors[i] = (int *) malloc(sizeof(int) * len[i]);
        for (x = 1, j = 0, len[i] = 0; j <= c; j++, x *= L[i]){
            for (d = 0; d < len[k]; d++){
                divisors[i][len[i]++] = divisors[k][d] * x;
            }
        }
    }
}
int main(){
    Generate();
    return 0;
}



/// Bernoulli Numbers
#define MAX 2510
#define MOD 1000000007
int S[MAX][MAX], inv[MAX], factorial[MAX], bernoulli[MAX];
int expo(long long x, int n){
    long long res = 1;
    while (n){
        if (n & 1) res = (res * x) % MOD;
        x = (x * x) % MOD;
        n >>= 1;
    }
    return (res % MOD);
}
void Generate(){
    int i, j;
    long long x, y, z, lim = (long long)MOD * MOD;
    for (i = 1, factorial[0] = 1; i < MAX; i++) factorial[i] = ((long long) factorial[i - 1] * i) % MOD;
    for (i = 0; i < MAX; i++) inv[i] = expo(i, MOD - 2);
    for (i = 1, S[0][0] = 1; i < MAX; i++){
        for (j = 1, S[i][0] = 0; j <= i; j++) S[i][j] = ( ((long long)S[i - 1][j] * j) + S[i - 1][j - 1]) % MOD;
    }
    bernoulli[0] = 1;
    for (i = 1; (i + 1) < MAX; i++){
        if ((i & 1) && i > 1) bernoulli[i] = 0;
        else{
            for (j = 0, x = 0, y = 0; j <= i; j++){
                z = ((long long) factorial[j] * inv[j + 1]) % MOD;
                z = (z * S[i][j]) % MOD;
                if (j & 1) y += z;
                else x += z;
            }
            bernoulli[i] = (lim + x - y) % MOD;
        }
    }
}
int main(){
    Generate();
    printf("%d\n", bernoulli[10]);
    return 0;
}