There are n people participating in some contest, they start participating in x minutes intervals. That means the first participant starts at time 0, the second participant starts at time x, the third — at time 2 ⋅ x, and so on.

Duration of contest is t minutes for each participant, so the first participant finishes the contest at time t, the second — at time t + x, and so on. When a participant finishes the contest, their dissatisfaction equals to the number of participants that started the contest (or starting it now), but haven't yet finished it.

Determine the sum of dissatisfaction of all participants.

Input

The first line contains a single integer k (1 ≤ k ≤ 1000) — the number of test cases.

Each of the next k lines contains three integers n, x, t (1 ≤ n, x, t ≤ 2 ⋅ 10^9) — the number of participants, the start interval and the contest duration.

Output

Print k lines, in the i-th line print the total dissatisfaction of participants in the i-th test case.

Example

Input


4
4 2 5
3 1 2
3 3 10
2000000000 1 2000000000


Output


5
3
3
1999999999000000000

Note

In the first example the first participant starts at 0 and finishes at time 5. By that time the second and the third participants start, so the dissatisfaction of the first participant is 2. 

The second participant starts at time 2 and finishes at time 7. By that time the third the fourth participants start, so the dissatisfaction of the second participant is 2. 

The third participant starts at 4 and finishes at 9. By that time the fourth participant starts, so the dissatisfaction of the third participant is 1.

The fourth participant starts at 6 and finishes at 11. By time 11 everyone finishes the contest, so the dissatisfaction of the fourth participant is 0.

In the second example the first participant starts at 0 and finishes at time 2. By that time the second participants starts, and the third starts at exactly time 2. So the dissatisfaction of the first participant is 2. 

The second participant starts at time 1 and finishes at time 3. At that time the third participant is solving the contest.

#include<bits/stdc++.h>
#include<iostream>
#define mi map<int,int>
#define umi unordered_map<int,int>
#define pii pair<int,int>
#define pll pair<long long int,long long int>
#define si  set<int>
#define st stack<int>
#define di deque<int>
#define qi queue<int> 
#define pq priority_queue<int>
#define dl deque<long long int>
#define usi unordered_set<int>
#define vi vector<int>
#define vl vector<long long int>
#define ll long long int
#define pb push_back
#define mk make_pair
#define all(v) v.begin(),v.end()
#define IOS  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define M1 1000000007
#define M2 998244353
#define I1 1000000001
#define I2 1000000000000000001
#define rev(v) reverse(v.begin(),v.end());
#define asort(v) sort(v.begin(),v.end())
#define dsort(v) sort(v.begin(),v.end(),greater<int>())
double PI=3.14159265358979323846;
using namespace std;
ll gcd(ll a,ll b){if(b==0) return a;else return gcd(b,a%b);}
 
bool isprime(ll a)
{ 
  if(a==1) return false;
  for(int i=2;i<=sqrt(a);i++)
  { 
    if(a%i==0) return false;
  } 
  return true;
}
ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}
 
// the number of zeros at the beginning of the bit representation //
 
int prefixzero(int x) {return __builtin_clz(x);}
 
// the number of zeros at the end of the bit representation //
int suffixzero(int x) {return __builtin_ctz(x);}
 
// the number of ones in the bit representation //
int numberone(int x) {return __builtin_popcount(x);}
// push the value of array element //
 
void read(vector<int> &v,int n) {for(int i=0;i<n;i++) cin>>v[i];}
 
void readl(vector<ll> &v,ll n) {for(ll i=0;i<n;i++) cin>>v[i];}
 
// to check the given number prime or not //
vector<bool>sprime(int n)
{
  vector<bool>prime(n+1,true);
  prime[0]=false;
  prime[1]=false;
  for(ll i=2;i*i<=n;i++)
  {
    if(prime[i])
    { 
      for(ll j=i*i;j<=n;j+=i) prime[j]=false;
    }
  }
  return prime;
}
// return the value of x and y in given equation of ax+by=gcd(a,b) //
tuple<int,int,int> GCD(int a,int b)
{
  if(b==0) return {1,0,a};
  else
  {
    int x,y,g;
    tie(x,y,g)=GCD(b,a%b);
    return {y,x-(a/b)*y,g};
  }
}

// to find the power of given number in logn time //
ll pw(ll base,ll power,ll mode)
{
  ll res=1;
  base=base%mode;
  while(power!=0)
  {
    if(power&1) {power-=1;res=(res*base)%mode;}
    else {power/=2;base=(base*base)%mode;}
  }
  return res;
}

// return total prime factor//
vector<ll>factor(ll n)
{
  vl fac;
  for(ll i=2;i<=sqrt(n);i++)
  {
    while(n%i==0)
    {
      fac.pb(i);
      n/=i;
    }
  }
  if(n!=1) fac.pb(n);
  return fac;
}

// the equation ax+by=c give the positive solution or not //
bool sol(ll a,ll b,ll c)
{
  if(c%gcd(a,b)==0)
  {
    ll m=c/gcd(a,b);
    double x1,y1,g;
    tie(x1,y1,g)=GCD(a,b);
    x1*=m;
    y1*=m;
    // general solution xi=x1+i(b/g),yi=y1-i(a/g) where i belong (-inf,inf)// 
    ll x2=ceil(-1.0*x1*(g/b));
    ll y2=floor(y1*(g/a)*1.0);
    if(x2<=y2) return true;
  }
  return false;
}

// return the fn and fn+1 of fibonacci number//
pair<ll,ll>fib(ll n)
{
  if(n==0) return {0,1};
  auto p=fib(n>>1);
  ll c =p.first*(2 *p.second-p.first);
  ll d =p.first*p.first+p.second*p.second;
  if (n & 1) return {d,c + d};
  else return {c,d};     
}
// hash the string in given string //
ll gethash(string &keys)
{
  ll p=31;
  ll m=1e9+9;
  ll hash_value=0;
  ll p_pow=1;
  for(char c:keys)
  {
    hash_value=(hash_value+(c-'a'+1)*p_pow)%m;
    p_pow=(p_pow*p)%m;
  }
  return hash_value;
}
// return the proper prifix array of given string //
vector<int>p_prefix(string s)
{
  int n=s.size();
  vector<int>pi(n);
  int j=0;
  for(int i=1;i<n;i++)
  {
    j=pi[i-1];
    while(j>0&&s[i]!=s[j]) j=pi[j-1];
    if(s[i]==s[j]) j++;
    pi[i]=j;
  }
  return pi;
}
// dfs traversal for graph and find the minimum distance from root node //
/*void dfs(int node,int d)
{
  visit[node]=1;
  dist[node]=d;
  for(int child:ar[node])
  {
    if(visit[child]==0) dfs(child,dist[node]+1);
  }
}*/
 
// bfs traversal for graph and find the minimum distance from root node //
/*void bfs(int node)
{
  queue<int>q;
  q.push(node);
  visit[node]=1;
  dist[node]=0;
  while(!q.empty())
  {
    int curr=q.front();
    q.pop();
    for(int child:ar[curr])
    {
      if(visit[child]==0)
      {
        q.push(child);
        dist[child]=dist[curr]+1;
        visit[child]=1;
      }
    }
  }
}*/
 
//---------------------------------START THE CODE------------------------------//
void solve()
{
  ll n,x,t;cin>>n>>x>>t;
  ll cnt=t/x;
  ll sum=max(0ll,n-cnt)*cnt+min(n-1,cnt-1)*min(cnt,n)/2;
  cout<<sum<<"\n";













  return;
}
int main()
{
    IOS;
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ll t=1;cin>>t;
    while(t--) {solve();}
  return 0;
}
/*-----------------END OF CODE------------------*/