Problem: There are n digital panels placed in a straight line. Each panel can show any digit from 0 to 9. Initially, all panels show 0.

Every second, the digit shown by each panel increases by 1. In other words, at the end of every second, a panel that showed 9 would now show 0, a panel that showed 0 would now show 1, a panel that showed 1 would now show 2, and so on.

When a panel is paused, the digit displayed on the panel does not change in the subsequent seconds.

You must pause exactly one of these panels, at any second you wish. Then, the panels adjacent to it get paused one second later, the panels adjacent to those get paused 2 seconds later, and so on. In other words, if you pause panel x, panel y (for all valid y) would be paused exactly |x−y| seconds later.

For example, suppose there are 4 panels, and the 3-rd panel is paused when the digit 9 is on it.

  * The panel 1 pauses 2 seconds later, so it has the digit 1; 
  * the panel 2 pauses 1 second later, so it has the digit 0; 
  * the panel 4 pauses 1 second later, so it has the digit 0. 



The resulting 4-digit number is 1090. Note that this example is not optimal for n = 4.

Once all panels have been paused, you write the digits displayed on them from left to right, to form an n digit number (it can consist of leading zeros). What is the largest possible number you can get? Initially, all panels show 0.

Input

The first line of the input contains a single integer t (1 ≤ t ≤ 100) — the number of test cases. Each test case consists of a single line containing a single integer n (1 ≤ n ≤ 2⋅10^5).

It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5.

Output

For each test case, print the largest number you can achieve, if you pause one panel optimally.

Example

Input


2
1
2


Output


9
98

Note

In the first test case, it is optimal to pause the first panel when the number 9 is displayed on it.

In the second test case, it is optimal to pause the second panel when the number 8 is displayed on it.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define ll unsigned long long
#define pi 3.141592653
#define pb push_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define F first
#define S second

using namespace std;


// Multiplies str1 and str2, and prints result. 
string multiply(string num1, string num2) 
{ 
	int len1 = num1.size(); 
	int len2 = num2.size(); 
	if (len1 == 0 || len2 == 0) 
	return "0"; 

	// will keep the result number in vector 
	// in reverse order 
	vector<int> result(len1 + len2, 0); 

	// Below two indexes are used to find positions 
	// in result. 
	int i_n1 = 0; 
	int i_n2 = 0; 
	
	// Go from right to left in num1 
	for (int i=len1-1; i>=0; i--) 
	{ 
		int carry = 0; 
		int n1 = num1[i] - '0'; 

		// To shift position to left after every 
		// multiplication of a digit in num2 
		i_n2 = 0; 
		
		// Go from right to left in num2			 
		for (int j=len2-1; j>=0; j--) 
		{ 
			// Take current digit of second number 
			int n2 = num2[j] - '0'; 

			// Multiply with current digit of first number 
			// and add result to previously stored result 
			// at current position. 
			int sum = n1*n2 + result[i_n1 + i_n2] + carry; 

			// Carry for next iteration 
			carry = sum/10; 

			// Store result 
			result[i_n1 + i_n2] = sum % 10; 

			i_n2++; 
		} 

		// store carry in next cell 
		if (carry > 0) 
			result[i_n1 + i_n2] += carry; 

		// To shift position to left after every 
		// multiplication of a digit in num1. 
		i_n1++; 
	} 

	// ignore '0's from the right 
	int i = result.size() - 1; 
	while (i>=0 && result[i] == 0) 
	i--; 

	// If all were '0's - means either both or 
	// one of num1 or num2 were '0' 
	if (i == -1) 
	return "0"; 

	// generate the result string 
	string s = ""; 
	
	while (i >= 0) 
		s += std::to_string(result[i--]); 

	return s; 
} 



int isPrime(ll n) 
{ 
    // Corner case 
    if (n <= 1) 
        return 0; 
  
    // Check from 2 to n-1 
    for (ll i = 2; i < n; i++) 
        if (n % i == 0) 
            return 0; 
  
    return 1; 
} 
ll modFact(ll n, ll p) 
{ 
    if (n >= p) 
        return 0; 
  
    ll result = 1; 
    for (ll i = 1; i <= n; i++) 
        result = (result * i) % p; 
  
    return result; 
}
// length of str1 and n is length of str2 
bool isSubSequence(string str1, string str2, int m, int n) 
{ 
    // Base Cases 
    if (m == 0) return true; 
    if (n == 0) return false; 
  
    // If last characters of two strings are matching 
    if (str1[m-1] == str2[n-1]) 
        return isSubSequence(str1, str2, m-1, n-1); 
  
    // If last characters are not matching 
    return isSubSequence(str1, str2, m, n-1); 
} 



// Returns true if s1 is substring of s2
ll isSubstring(string s1, string s2)
{
	ll M = s1.length();
	ll N = s2.length();

	/* A loop to slide pat[] one by one */
	for (ll i = 0; i <= N - M; i++) {
		ll j;

		/* For current index i, check for
pattern match */
		for (j = 0; j < M; j++)
			if (s2[i + j] != s1[j])
				break;

		if (j == M)
			return i;
	}

	return -1;
}

// C++ program to compute factorial of big numbers 
#include<iostream> 
using namespace std; 

// Maximum number of digits in output 
#define MAX 500 

int multiply(int x, int res[], int res_size); 

// This function finds factorial of large numbers 
// and prints them 
void factorial(int n) 
{ 
	int res[MAX]; 

	// Initialize result 
	res[0] = 1; 
	int res_size = 1; 

	// Apply simple factorial formula n! = 1 * 2 * 3 * 4...*n 
	for (int x=2; x<=n; x++) 
		res_size = multiply(x, res, res_size); 

//	cout << "Factorial of given number is \n"; 
	for (int i=res_size-1; i>=0; i--) 
		cout << res[i]; 
} 

// This function multiplies x with the number 
// represented by res[]. 
// res_size is size of res[] or number of digits in the 
// number represented by res[]. This function uses simple 
// school mathematics for multiplication. 
// This function may value of res_size and returns the 
// new value of res_size 
int multiply(int x, int res[], int res_size) 
{ 
	int carry = 0; // Initialize carry 

	// One by one multiply n with individual digits of res[] 
	for (int i=0; i<res_size; i++) 
	{ 
		int prod = res[i] * x + carry; 

		// Store last digit of 'prod' in res[] 
		res[i] = prod % 10; 

		// Put rest in carry 
		carry = prod/10;	 
	} 

	// Put carry in res and increase result size 
	while (carry) 
	{ 
		res[res_size] = carry%10; 
		carry = carry/10; 
		res_size++; 
	} 
	return res_size; 
} 



int main(){

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ll t;
  cin>>t;
  while(t--)
  {
      ll n;
      cin>>n;
      if(n==1)
      cout<<9<<endl;
      else if(n==2)
      cout<<"98"<<endl;
      else if(n==3)
      cout<<989<<endl;
      else
      {
          cout<<989;
          ll a=0;
          for(ll i=0;i<n-3;i++)
          {
              cout<<a;
              a=(a+11)%10;
          }
          cout<<endl;
      }
  }



    return 0;
}