#include <bits/stdc++.h>
using namespace std;
#define InTheNameOfGod ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
using ll = long long;

const int maxN = 500;
const int MOD = 1e9 + 7;

int dp[1100][501][501];


int main() {
    #pragma region
#ifndef ONLINE_JUDGE
   freopen("../input.txt", "r", stdin);
   freopen("../output.txt", "w", stdout);
#endif

   InTheNameOfGod;
#pragma endregion
  
    vector<pair<int, int>> v;

    for(int i = 1; i <= 30; i++) {
        for(int j = 1; j <= 30; j++) {
            if(__gcd(i, j) == 1) v.push_back({i, j});
        }
    }

    return 0;


    /*for(int i = 1; i <= v.size(); i++) {
        for(int j = 1; j <= maxN; j++) {
            for(int l = 1; l <= maxN; l++) {
                if(v[i-1].first <= j && v[i-1].second <= l) {
                    dp[i][j][l] = max(dp[i-1][j][l], dp[i-1][j - v[i-1].first][l - v[i-1].second] + 1);
                }
                else {
                    dp[i][j][l] = dp[i-1][j][l];
                }
            }
        }
    }

    int t;
    cin >> t;
    while(t--) {
        int x,y;
        cin >> x >> y;

        cout << dp[v.size()][x][y] << "\n";
    }

    return 0;*/
}