#include <iostream>
#include <vector>
#include <cstdint>
#include <numeric>

std::vector<std::pair<int, int>> beolvas(std::istream &be) {
    int n;
    be >> n;

    std::vector<std::pair<int, int>> kerdesek(n);
    for (auto &[k, m] : kerdesek) {
        be >> k >> m;
    }

    return kerdesek;
}

void feldolgoz(const std::vector<std::pair<int, int>> &kerdesek) {
    const int m = 32;
    const int n = 500;

    std::vector<std::vector<uint32_t>> dp(n + 1, std::vector<uint32_t>(n + 1, 0));
    for (int a = 1; a <= m; a++) {
        for (int b = 1; b <= m; b++) {
            if (std::gcd(a, b) == 1) {
                for (int i = n; i >= a; i--) {
                    for (int j = n; j >= b; j--) {
                        dp[i][j] = std::max(dp[i][j], dp[i - a][j - b] + 1);
                    }
                }
            }
        }
    }

    for (auto [k, m] : kerdesek) {
        std::cout << dp[k][m] << '\n';
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    const auto kerdesek = beolvas(std::cin);
    feldolgoz(kerdesek);

    return 0;
}