#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; #ifdef LOCAL # include <debug_print.hpp> # define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else # define debug(...) (static_cast<void>(0)) #endif long long solve() { long long N, S, K; N = 1e9; cin >> K >> S; if(S % N == 0 && K % N == 0){ return 1; } S %= N; K %= N; debug(S, K, N); auto p = crt({0, N - S}, {K, N}); if (p.second == 0) return -1; debug(p, N); return p.first / K; } int main(){ int T; cin >> T; while (T--) cout << solve() << endl; }