// https://yukicoder.me/problems/no/302 // status: // tag: [multi_choose] #define SUBMIT //#define DEBUG #include using namespace std; using ui64 = unsigned long long; using i64 = long long; const int MAX_D = 1500; const int MAX_K = 1500; ui64 dp[(MAX_D + MAX_K - 1) + 1][MAX_K + 1]; // dp[i][j] i種類の品物を重複ありでj個選ぶ組み合わせの総数 // nC0 = 1 // 重複組合せではnHk = n+k-1Ck // nCk = n-1Cr-1 + n-1Crの公式を用いる // dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][r]; template void init_multi_choose(T dp[N][K], ui64 mod) { for (int i = 0; i < N; ++i) dp[i][0] = 1; for (int i = 0; i < N - 1; ++i) { for (int j = 1; j < K; ++j) { dp[i + 1][j] = (dp[i + 1][j] + dp[i][j - 1] + dp[i][j]) % mod; } } } template void init_multi_choose(T dp[N][K]) { for (int i = 0; i < N; ++i) dp[i][0] = 1; for (int i = 0; i < N - 1; ++i) { for (int j = 1; j < K; ++j) { dp[i + 1][j] = (dp[i + 1][j] + dp[i][j - 1] + dp[i][j]); if (dp[i + 1][j] > Limit) dp[i + 1][j] = Limit; } } } const ui64 LIMIT = static_cast(1e16); int main() { #ifdef SUBMIT auto& stream = cin; #else stringstream stream(R"(3 58 62 1000 12 34 56 987 65 1234 )"); #endif init_multi_choose(dp); ui64 Q; stream >> Q; ui64 D, K, T; for (int i = 0; i < Q; ++i) { stream >> D >> K >> T; auto n_runs = dp[D + K - 1][K]; if (T < n_runs) cout << "ZETUBOU" << endl; else cout << "AC" << endl; } return 0; }