/*
//! In The Name Of Allah
*/
#include<bits/stdc++.h>
using namespace std;
#define tt int t;cin>>t;while(t--)
#define itr(i,a) for(int i=0;i<a;i++)
#define ittr(i,bg,a) for(int i=bg;i<a;i++)
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define ll long long
#define endd cout<<endl
#define vc(v, n) vector<ll> v(n)
#define srt(v) sort(v.begin(), v.end())
#define rsrt(v) sort(v.rbegin(), v.rend())
#define pb(a,x) a.push_back(x)
#define MOD 1000000007
#define f first
#define sc second
#define endl '\n'
const int N=1e6+1;
vector<bool>isprime(N,false);
vector<ll>primes;
ll cnt_div[N]={0};
vector<ll>divisor[N];
void divis(){
for(int i=1;i<=N;i++){
for(int j=i;j<=N;j+=i){
cnt_div[j]++;
divisor[j].push_back(i);
//if(i/j!=i) divisor[j].push_back(i/j);
}
}
}
void sieve(){
isprime[1]=false;
isprime[2]=true;
pb(primes,2);
for(int i=3;i*i<=N;i+=2) isprime[i]=true;
for(int i=3;i<=N;i+=2){
if(isprime[i]){
pb(primes,i);
for(int j=i*i;j<=N;j+=i){
isprime[j]=false;
}
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
// sieve();
// divis();
tt{
}
}
CQkvKgoJCQkvLyEgSW4gVGhlIE5hbWUgT2YgQWxsYWgKCQkJCQoJCQkKCQkJCQoJCQkJCgkJKi8gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIAogICNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CiAgdXNpbmcgbmFtZXNwYWNlIHN0ZDsKICAjZGVmaW5lIHR0IGludCB0O2Npbj4+dDt3aGlsZSh0LS0pCiAgI2RlZmluZSBpdHIoaSxhKSBmb3IoaW50IGk9MDtpPGE7aSsrKQojZGVmaW5lIGl0dHIoaSxiZyxhKSBmb3IoaW50IGk9Ymc7aTxhO2krKykKICAjZGVmaW5lIHllcyBjb3V0PDwiWUVTIjw8ZW5kbAogICNkZWZpbmUgbm8gY291dDw8Ik5PIjw8ZW5kbAogICNkZWZpbmUgbGwgbG9uZyBsb25nCiAgI2RlZmluZSBlbmRkIGNvdXQ8PGVuZGwKICAjZGVmaW5lIHZjKHYsIG4pIHZlY3RvcjxsbD4gdihuKSAgCiAgI2RlZmluZSBzcnQodikgc29ydCh2LmJlZ2luKCksIHYuZW5kKCkpCiNkZWZpbmUgcnNydCh2KSBzb3J0KHYucmJlZ2luKCksIHYucmVuZCgpKQojZGVmaW5lIHBiKGEseCkgYS5wdXNoX2JhY2soeCkKI2RlZmluZSBNT0QgMTAwMDAwMDAwNwogICNkZWZpbmUgZiBmaXJzdAogICNkZWZpbmUgc2Mgc2Vjb25kCiNkZWZpbmUgZW5kbCAnXG4nCmNvbnN0IGludCBOPTFlNisxOwp2ZWN0b3I8Ym9vbD5pc3ByaW1lKE4sZmFsc2UpOwp2ZWN0b3I8bGw+cHJpbWVzOwpsbCBjbnRfZGl2W05dPXswfTsKdmVjdG9yPGxsPmRpdmlzb3JbTl07CnZvaWQgZGl2aXMoKXsKZm9yKGludCBpPTE7aTw9TjtpKyspewpmb3IoaW50IGo9aTtqPD1OO2orPWkpewpjbnRfZGl2W2pdKys7CmRpdmlzb3Jbal0ucHVzaF9iYWNrKGkpOwovL2lmKGkvaiE9aSkgZGl2aXNvcltqXS5wdXNoX2JhY2soaS9qKTsKfQp9Cgp9CnZvaWQgc2lldmUoKXsKaXNwcmltZVsxXT1mYWxzZTsKaXNwcmltZVsyXT10cnVlOwpwYihwcmltZXMsMik7CmZvcihpbnQgaT0zO2kqaTw9TjtpKz0yKSBpc3ByaW1lW2ldPXRydWU7CmZvcihpbnQgaT0zO2k8PU47aSs9Mil7CmlmKGlzcHJpbWVbaV0pewpwYihwcmltZXMsaSk7CmZvcihpbnQgaj1pKmk7ajw9TjtqKz1pKXsKaXNwcmltZVtqXT1mYWxzZTsKfQp9Cn0KfQoKICBpbnQgbWFpbigpewogICAgaW9zOjpzeW5jX3dpdGhfc3RkaW8oZmFsc2UpOwogICAgICBjaW4udGllKG51bGxwdHIpOwogICAgLy8gc2lldmUoKTsKICAgLy8gZGl2aXMoKTsKICB0dHsKIAoKICB9CiAgfQogIAoK