View Code of Problem 3938

#include <iostream>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <string>
#include <map>
#include <bitset>
#include <sstream>

using namespace std;


typedef long long ll;
const ll mod = 1e9 + 7;

int R[10] = {2, 3, 5, 7, 11, 13, 17, 19};
int f[1010];
int g[1010];


void init() {
    for (int s = 1; s < (1 << 8); s++) {
        f[s] = 1, g[s] = 0;
        for (int j = 0; j < 8; j++)
            if ((s >> j) & 1) {
                f[s] = f[s] * R[j];
                g[s]++;
            }
    }

}

int main() {
    int t;
    init();
    scanf("%d", &t);
    while(t--) {
        ll x, y, n, m;
        scanf("%lld%lld%lld%lld", &x, &y, &n, &m);
        int k = -1;
        while (k + 1 < 8 && R[k + 1] <= m) k++;
        k++;
        ll cnt = 0;
        for(int i = 1; i < (1 << k); i++) {
            if(g[i] & 1) cnt += 1ll * n / f[i];
            else cnt -= 1ll * n / f[i];
        }
        if(n - cnt + min(y, cnt) >= x) printf("(*^_^*)\n");
        else printf("(ToT)\n");
    }
    return 0;
}