Roy and Alfi are playing a game with three 1000-sided dice. Each die has 1000 faces and all the faces are marked from 1 to 1000 on each die.

Alfi rolls all three dice together and sums up the score on all three dice. Total score of Alfi is denoted by A. Now it is Roy’s turn to roll them. Let us denote Roy’s score as R, which is sum of scores on all 3 dice.

You have to find the number of ways in which R ≥ A.

Input:
First line contains T – number of test cases.
Each of the next T lines contains a single integer A – total score of Alfi.

Output:
For each test case output the result in a new line.

Constraints:
1 ≤ T ≤ 10
3 ≤ A ≤ 3000

Sample Input

```3
3
4
3000
```
Sample Output

```1000000000
999999999
1

```
Explanation

For three 1000-sided dice, the sample space would consist of 1000000000 ways.
These ways are (1,1,1), (1,1,2), (1,2,1), (2,1,1), … , … , … , (1000,1000,1000).

Test #1:
Sum of three dices such that it is greater than equal to 3.
This is satisfied by all the ways in the sample space. So the answer is 1000000000.

Test #2:
Sum of three dices such that it is greater than equal to 4.
This is not satisfied by only way (1,1,1) out of 1000000000 ways. So the answer is 1000000000 – 1 = 999999999.

Test #3:
Sum of three dices such that it is greater than equal to 3000.
Only way that satisfied this is (1000,1000,1000). Hence the answer is 1.

#include<bits/stdc++.h>
using namespace std;

#define ll long long int

int findWays(int m, int n, int x)
{

int table[n + 1][x + 1];
memset(table, 0, sizeof(table)); // Initialize all entries as 0

for (int j = 1; j <= m && j <= x; j++)
table[1][j] = 1;

for (int i = 2; i <= n; i++)
for (int j = 1; j <= x; j++)
for (int k = 1; k <= m && k < j; k++)
table[i][j] += table[i-1][j-k];

/* Uncomment these lines to see content of table
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= x; j++)
cout << table[i][j] << ” “;
cout << endl;
}*/
return table[n][x];
}
double solve(int m, int n, int x) //m : range; n , dices, x threshold.
{
if (x > m*n || x < n)
return 0;
vector<vector<int>> dp(2, vector<int>(m * n + 1));
for (int i = 0; i <= m * n; ++i)
dp[0][i] = min(i, m);
for (int i = 1; i < n; ++i)
{
fill(&dp[i%2][0], &dp[i%2][i], 0);
for (int j = i; j <= m * n; ++j)
dp[i%2][j] = dp[i%2][j – 1] + dp[(i – 1)%2 ][j – 1] – dp[(i – 1)%2 ][j – 1 – min(j – 1 , m)];
}
return double(dp[(n – 1)%2][m*n] – dp[(n-1)%2][x]) / dp[(n – 1)%2][m*n];
}

int main()
{

ll n,a,r,sum=0;
cin>>n;
while(n–)
{
cin>>a;
if(a==3000)
{
cout<<1<<endl;
continue;
}
for(int i=0;i<a;i++)
{
sum+=findWays(1000,3,i);
}
cout<<solve(1000,3,a);
cout<<1000000000-sum<<endl;
}

return 0;
}