#include using namespace std; #define ll long long #define rep(i,n) for(int i=0;i=0;i--) #define rrep2(i,n,k) for(int i=n-1;i>=n-k;i--) #define vll(n,i) vector(n,i) #define v2ll(n,m,i) vector>(n,vll(m,i)) #define v3ll(n,m,k,i) vector>>(n,v2ll(m,k,i)) #define v4ll(n,m,k,l,i) vector>>>(n,v3ll(m,k,l,i)) #define all(v) v.begin(),v.end() #define chmin(k,m) k = min(k,m) #define chmax(k,m) k = max(k,m) #define Pr pair #define Tp tuple #define riano_ std::ios::sync_with_stdio(false);std::cin.tie(nullptr) #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //Graph struct graph { long long N; vector>> G; vector par_v; vector par_e; int edge_count = 0; graph(long long n) { N = n; G = vector>>(N); par_v = vector(N,-1); par_e = vector(N,-1); } void unite(long long a,long long b,long long cost = 1,bool directed = false){ G[a].emplace_back(b,cost,edge_count); if(!directed) G[b].emplace_back(a,cost,edge_count); edge_count++; } }; const ll mod = 1e9+7; template struct modint{ uint64_t val; constexpr modint(const int64_t val_=0) noexcept:val((val_%int64_t(mod)+int64_t(mod))%int64_t(mod)){} constexpr modint operator-() const noexcept{ return modint(*this)=mod-val; } constexpr modint operator+(const modint rhs) const noexcept{ return modint(*this)+=rhs; } constexpr modint operator-(const modint rhs) const noexcept{ return modint(*this)-=rhs; } constexpr modint operator*(const modint rhs) const noexcept{ return modint(*this)*=rhs; } constexpr modint operator/(const modint rhs) const noexcept{ return modint(*this)/=rhs; } constexpr modint &operator+=(const modint rhs) noexcept{ val+=rhs.val; val-=((val>=mod)?mod:0); return (*this); } constexpr modint &operator-=(const modint rhs) noexcept{ val+=((val>=1; } return (*this)*=now; } modint & operator++(){ val++; if (val == mod) val = 0; return *this; } modint operator++(int){ modint res = *this; ++*this; return res; } constexpr bool operator==(const modint rhs) noexcept{ return val==rhs.val; } constexpr bool operator!=(const modint rhs) noexcept{ return val!=rhs.val; } friend constexpr ostream &operator<<(ostream& os,const modint x) noexcept{ return os<<(x.val); } friend constexpr istream &operator>>(istream& is,modint& x) noexcept{ uint64_t t; is>>t,x=t; return is; } }; typedef modint mint; mint pw(long long a,long long b,long long m = mod){ if(a%m==0) return mint(0); if(b==0) return mint(1); else if(b%2==0){ long long x = pw(a,b/2,m).val; return mint(x*x); } else{ long long x = pw(a,b-1,m).val; return mint(a*x); } } mint modinv(long long a, long long m = mod) { long long b = m, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; return mint(u); } #define vm(n,i) vector(n,i) #define v2m(n,m,i) vector>(n,vm(m,i)) #define v3m(n,m,k,i) vector>>(n,v2m(m,k,i)) #define v4m(n,m,k,l,i) vector>>>(n,v3m(m,k,l,i)) void out(vector &v){ for(ll x:v) cout << x << " "; cout << "\n"; return; } int main(){ riano_; mint ans = 0; ll N,M,K,H,W,Q,L,R,T; cin >> T; rep(ii,T){ ll a; cin >> a >> N; ans = 0; ll len = 3; ll r = 0; mint s = 0; ll f = 0; rep(i,a){ s += mint(i+1)*mint((len+r)/a); f += (len+r)/a; r = (len+r)%a; len += 2; } //解から二分探索 binary search //分かれ目の"r"側の値を求める ll l,rr; l = 0; rr = min(N/f+1,(ll)1e6+1); //初期値の代入 while(l=1;i--){ ans += (mint(3*a+1)+mint(2*a)*mint(l-1-i))*mint(a)*mint(i); } len = 3+2*a*l; r = 0; rep(i,a){ ll tmp = (len+r)/a; if(tmp>N){ ans += mint(N)*mint(l*a+(ll)(1+i)); break; } else{ ans += mint(tmp)*mint(l*a+(ll)(1+i)); N -= tmp; } r = (len+r)%a; len += 2; } cout << ans << endl; } //cout << ans << endl; }