#include<bits/stdc++.h>
using namespace std;
//#include<atcoder/all>
//using namespace atcoder;
using ll = long long;
#define For(i,n,k) for(int i=(n);i<(k);i++)
#define ALL(a) (a).begin(),(a).end()
void solve(vector<vector<int>> &A, vector<vector<int>> &B, int num){
    vector<vector<int>> retA(num - 1), retB(num - 1);
    For(i,0,A.size()){
        retA[i] = A[i];
        retA[i+A.size()] = A[i];
    }
    int idx = 0;
    for(int i=0; i<A.size(); i++){
        for(auto &e: A[i]) retA[idx].emplace_back(e + num / 2);
        idx++;
    }
    for(int i=0; i<B.size(); i++){
        for(auto &e: B[i]) retA[idx].emplace_back(e + num / 2);
        idx++;
    }
    retA[num - 2].clear();
    For(i,0,num/2){
        retA[num - 2].emplace_back(i);
    }
    For(i,0,num - 1){
        int t = 0;
        for(auto &a: retA[i]){
            while(t < a){
                retB[i].emplace_back(t);
                t++;
            }
            t++;
        }
        while(t < num){
            retB[i].emplace_back(t);
            t++;
        }
    }
    swap(A, retA);
    swap(B, retB);
}
void Print(vector<vector<int>> &A, vector<vector<int>> &B, int num){
    cout << A.size() << endl;
    For(i,0,A.size()){
        string ret(num, 'B');
        for(auto c:A[i]) ret[c] = 'A';
        cout << ret << endl;
    }
}
void Main(){
    int tn;
    cin >> tn;
    int n = (1 << tn);
    vector<vector<int>> A(1, {0}), B(1, {1});
    for(int num = 2; num < n; num *= 2){
        solve(A, B, num * 2);
    }
    /*
    for(int i=0; i<A.size(); i++){
        for(auto t:A[i]) cout << t << " ";
        cout << "vs ";
        for(auto t:B[i]) cout << t << " ";
        cout << endl;
    }
    cout << A.size() << " " << B.size() << endl;
    */
    Print(A, B, n);
}
void Editorial(){
    int n;
    cin >> n;
    cout << ((1<<n)-1) << endl;;
    For(i,1,1<<n){
        For(j,0,1<<n){
            cout << (__builtin_parity(i & j) ? 'A' : 'B');
        }
        cout << endl;
    }
}
int main(){
    // Main();
    Editorial();
    /*
    東方風神録は神が出てくるので当然神ゲー
    */
    return 0;
}
#include<bits/stdc++.h>

using namespace std;
typedef pair<int, int> P;
typedef long long ll;

int gcd(ll x, ll y){
    if(x < y)swap(x, y);
    if(x % y == 0)return y;
    return gcd(y, x % y);
}

int extgcd(ll a, ll b, ll &x, ll &y){
    int d = a;
    if(b != 0){
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }else{
        x = 1; y = 0;
    }
    return d;
}

int main(){
    int t;
    cin >> t;
    vector<ll> ans(t);
    for(int i = 0; i < t; i++){
        ll n, s, k;
        cin >> n >> s >> k;
        ll div = gcd(n, k);
        if(s % div != 0){
            ans[i] = -1;
            continue;
        }
        n /= div;
        s /= div;
        k /= div;
        ll x, y;
        if(k > n) extgcd(k, n, x, y);
        else extgcd(n, k, y, x);
        ll m;
        if(- s * x > 0){
            if(s * x % n == 0){
                m = - s * x / n - 1;
            }else{
                m = - s * x / n;
            }
        }else{
            if(s * x % n == 0){
                m = - s * x / n - 1;
            }else{
                m = - s * x / n - 1;
            }
        }
        ans[i] = - n * m - s * x;
    }
    for(int i = 0; i < t; i++){
        cout << ans[i] << endl;
    }
    return 0;
}