#pragma region Macros #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define OVERLOAD(e1, e2, e3, e4, NAME, ...) NAME #define _rep1(i, n) for (long long i = 0; i < n; i++) #define _rep2(i, a, b) for (long long i = a; i < b; ++i) #define _rep3(i, a, b, t) \ for (long long i = a; i * (t / abs(t)) < b * (t / abs(t)); i += t) #define rep(...) OVERLOAD(__VA_ARGS__, _rep3, _rep2, _rep1, _)(__VA_ARGS__) #define all(x) (x).begin(), (x).end() #define sz(x) (ll) x.size() #define fi first #define se second #define pb push_back #define eb emplace_back #define mp make_pair #define pcnt __builtin_popcountll #define SORT(v) sort(all(v)) #define UNIQUE(v) \ SORT(v); \ v.erase(unique(v.begin(), v.end()), v.end()); #define COPY(A, B) copy(all(A), B.begin()); #define REV(v) reverse(all(v)) #define MAX(x) *max_element(all(x)) #define MIN(x) *min_element(all(x)) #ifdef LOCAL #define dbg(...) \ { cout << __LINE__ << " : " << #__VA_ARGS__ << " = ", print(__VA_ARGS__); } #else #define dbg(...) true #endif using namespace std; template using vc = vector; template using vvc = vector>; template using vvvc = vector>; template bool chmin(T& k, U m) { bool ret = k > m; if (k > m) k = m; return ret; } template bool chmax(T& k, U m) { bool ret = k < m; if (k < m) k = m; return ret; } void print() { cout << "\n"; } template inline void print(const vector& v, string s = " ") { for (ll i = 0; i < (ll)v.size(); i++) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n"); } template inline void print(const vvc& v, string s = " ") { for (ll i = 0; i < (ll)v.size(); i++) print(v[i], s); } template inline void print(const set& vv) { for (ll v : vv) cout << v << " "; cout << "\n"; } template inline void print(const multiset& vv) { for (ll v : vv) cout << v << " "; cout << "\n"; } template inline void print(const pair& p) { cout << p.first << " " << p.second << endl; } template inline void print(const vector>& v) { for (auto&& p : v) print(p); } template void print(Head H, Tail... T) { cout << H << " "; print(T...); } template inline void print(const T& x) { cout << x << "\n"; } void yes(bool a) { cout << (a ? "yes" : "no") << endl; } void YES(bool a) { cout << (a ? "YES" : "NO") << endl; } void Yes(bool a) { cout << (a ? "Yes" : "No") << endl; } template T SUM(vc As) { T ret = 0; for (T a : As) ret += a; return ret; } #pragma endregion const ll INF = numeric_limits::max() / 2; unordered_map> icounter; ; void solve() { ll N; cin >> N; string S; cin >> S; ll n = stoll(S.substr(sz(S) - 3, 3)); unordered_map counter; ll cnt = 0; for (auto [k, vs] : icounter) { cnt += sz(vs); for (auto v : vs) { counter[k] += N / v; } } dbg(cnt); // for (auto [k, v] : counter) dbg(k, v); print(counter[n]); } int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(15); rep(i, 1, 1001) { rep(j, i + 1) { if (i != 1 && gcd(i, j) != 1) continue; icounter[1000 * j / i].eb(i); } } ll T; cin >> T; rep(_, T) solve(); }