#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cstdint>
#include <cstdio>
#include <bitset>
#include <deque>
#include <regex>
#include <list>
#include <unordered_map>
#include <unordered_set>

#define debug(a) std::cout<<#a<<"="<<(a)<<"\n"
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define rrep(i,x,y) for(int i=(x);i>=(y);i--)
#define mms(x) memset((x), 0, sizeof(x))
#define pb push_back
#define mkp std::make_pair
#define fi first
#define se second

using LL = long long;
using ULL = unsigned long long;
using DB = double;
using LD = long double;
using ui = unsigned;
using i128 = __int128;
using pii = std::pair<int,int>;
using pll = std::pair<LL,LL>;

int const MAXN = 200005;
int const INF = 0x7fffffff;
DB const EPS = 1e-8;
int const MOD = 998244353;
DB const PI = acos(-1);

int arr[MAXN];

void solve(){
    int n;
    std::cin>>n;
    for(int i=1;i<=n;i++){
        std::cin>>arr[i];
    }
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

	int T;
	std::cin>>T;
	//T=1;
	while(T--){
	    solve();
	}

    return 0;
}

//复杂度n
//kmp,luogu3375
std::vector<int> prefixFunc(std::string const & str){
    //输入一个字符串，输出该字符串的前缀函数表
    //前缀函数pi[i]是满足s[0...x-1]==s[i-x+1...i]的最大的x
    //如果输入不是字符串而是一个数组，也可以很方便的修改为vector
    int n = str.length();
    std::vector<int> ans(n);

    for(int i=1, j=0;i<n;i++){
        //ans[0]=0，因为只看真前缀和真后缀
        while(j && str[i]!=str[j]) j = ans[j-1];
        if(str[i]==str[j]) j++;
        ans[i] = j;
    }

    return ans;
}

std::vector<int> KMP(std::string const & s, std::string const & p){
    //输入主串和模式串，返回所有匹配的开始下标，下标从0开始
    std::vector<int> vec;
    std::vector<int> pf = prefixFunc(p);
    int ns = s.size(), np = p.size();
    for(int i=0, j=0;i<ns;i++){
        while(j && s[i]!=p[j]) j = pf[j-1];
        if(s[i]==p[j]) j++;
        if(j==np){
            vec.push_back(i-j+2);
            j = pf[j-1];
        }
    }
    
    return vec;
}

//我们可以通过把模式串和主串拼在一起，p+#+s，然后求这个字符串的前缀函数表（#代表不在主串、模式串字符集内的一个符号），然后pi[i]如果等于模式串的长度，那么i是匹配模式串的子串的起点。
//关于最小循环结，设字符串下标从1开始，长度为n，则如果n%(n-pf[n])==0，则有循环节，并且长度为n-pf[n]（当然长度可以为n）

//复杂度 插入或查找一次 模板串长度
//luogu p8306
class Trie{
public:
    int nxt[MAXM][26];
    int cnt;
    
    void init(){
        for(int i=0;i<=cnt;i++) for(int j=0;j<26;j++) nxt[i][j] = 0;
        cnt = 0;//起始节点编号为0
    }
    
    void insert(std::string const & s){
        int cur = 0;
        for(auto c:s){
            if(!nxt[cur][c-'a']){
                nxt[cur][c-'a']=++cnt;
            }
            cur = nxt[cur][c-'a'];
        }
    }
    
    bool find_prefix(std::string const & s){
        int cur=0;
        for(auto c:s){
            if (!nxt[cur][c-'a']){
               return false;
            }            
            cur = nxt[cur][c-'a'];
        }
        return true;
    }
};

Trie trie;

//自然溢出法，相当于对2^64取模的单哈希，是比较容易被特殊数据卡掉的
//luogu P3370
using ULL = unsigned long long;
ULL H(std::string const & str){
    ULL ret = 0;
    ULL const base = 131;//ascii也就128个字符，质数131作为底数足够
    
    for(auto c:str){
        ret = ret*base+(ULL)c;
    }
    return ret;
}

//双哈希法，两个字符串的两个哈希必须分别相同，才会被考虑为相同的字符串
//比起单哈希，更不容易被卡
//luogu P3370
ULL const MOD1 = 998244353;
ULL const MOD2 = 1e9+7;
ULL const base = 131;

struct Data{//把字符串的两个哈希捆起来，便于排序比较等操作
    ULL x,y;
};

ULL H1(std::string const & str){
    ULL ret = 0;
    for(auto c:str){
        ret = (ret*base+(ULL)c)%MOD1;
    }
    return ret;
}

ULL H2(std::string const & str){
    ULL ret = 0;
    for(auto c:str){
        ret = (ret*base+(ULL)c)%MOD2;
    }
    return ret;
}

//复杂度 文本串长度+模板串长度之和
//AC自动机，luogu P3808
//AC自动机会把Trie修改掉，并不是插入时候的字典树了，实际上变成了一张图+fail指针。
//trie数组表示从当前状态添加一个字符后到达的状态，fail数组表示，目前为止匹配，但是添加下一个字符后不匹配了，跳转至最长的后缀状态（不包括添加的下一个字符）。可以反复跳转。
//注意，一个状态是可行状态，当且仅当它自己可行，或者fail指针指向的状态可行，或者fail[fail]可行，以此类推

class AC{
public:
	int trie[MAXN][26], total;
	int end[MAXN],fail[MAXN];

    void init(int m){
        for(int i=0;i<=m;i++){
            end[i] = 0;
            fail[i] = 0;
            for(int j=0;j<26;j++) trie[i][j] = 0;
        }
        total = 0;
    }

	void insert(std::string const & str){
	    //插入模式串
		int u = 0;
		for(auto c:str){
			if(!trie[u][c-'a']){
				trie[u][c-'a'] = ++total;
			}
			u = trie[u][c-'a'];
		}
		end[u]++;
	}

	void buildFail(){
	    //构建fail指针
	    std::queue<int> qu;
		for(int i=0;i<26;i++){
			if(trie[0][i]) qu.push(trie[0][i]);
		}

		while(!qu.empty()){
			int u = qu.front();
			qu.pop();

			for(int i=0;i<26;i++){
				if(trie[u][i]){
					fail[trie[u][i]] = trie[fail[u]][i];	
					qu.push(trie[u][i]);
				}
				else{
					trie[u][i] = trie[fail[u]][i];
				}
			}
		}
	}

	int query(std::string const & str){
	    //查询主串str中出现了几个模式串
		int u = 0, res = 0;
		for(auto c:str){
			u = trie[u][c-'a'];
			for(int j = u ; j && end[j] != -1 ; j = fail[j]){
				res += end[j];
				end[j] = -1;
			}
		}

		return res;
	}
};

//最小表示法
//luogu P1368
//复杂度 O(n)
int arr[MAXN];

int minStr(int n){//数组下标从0开始，共n个；返回最小表示的开始下标
    int i=0, j=1, k=0;
    while(i<n && j<n && k<n){
        if(arr[(i+k)%n]==arr[(j+k)%n]){
            k++;
        }
        else if(arr[(i+k)%n]>arr[(j+k)%n]){//最大表示法时就把这一段和下一段换一下
            i += k+1;
            k = 0;
        }
        else{
            j += k+1;
            k = 0;
        }
        
        if(i==j) j++;
    }
    
    return std::min(i,j);
}

//manacher 算法
//luogu P3805
//复杂度O(n)
std::vector<int> getD1(std::string const & str){
    //返回字符串以某一位为中心的，最长的（奇数长度）回文子串的长度半径
    //例如abcba中，d1[2] = 3
    int n = str.size();
    std::vector<int> d(n);
    for(int i=0,l=0,r=-1;i<n;i++){
        int j = l+r-i;
        int dj = j>=0?d[j]:0;
        d[i] = std::max(std::min(dj,j-l+1),0);
        
        if(j-dj<l){
            while(i-d[i]>=0 && i+d[i]<n && str[i-d[i]]==str[i+d[i]])
                d[i]++;
            l = i-d[i]+1, r = i+d[i]-1;
        }
    }
    
    return d;
}

std::vector<int> getD2(std::string const & str){
    //返回字符串以某一位的左边间隙为中心的，最长的（偶数长度）回文子串的长度半径
    //例如abba中，d2[2] = 2
    int n = str.size();
    std::vector<int> d(n);
    for(int i=0,l=0,r=-1;i<n;i++){
        int j = l+r-i;
        int dj = j>=0?d[j]:0;
        d[i] = std::max(std::min(dj,j-l),0);
        
        if(j-dj-1<l){
            while(i-d[i]-1>=0 && i+d[i]<n && str[i-d[i]-1]==str[i+d[i]])
                d[i]++;
            l = i-d[i], r = i+d[i]-1;
        }
    }
    
    return d;
}

//Z函数，复杂度O(n)
//luogu P5410
std::vector<int> zFunc(std::string const & str){
    //求出一个字符串的z函数，即满足z[i]是s[0...x-1]==s[i...i+x-1]的最大的x，这个子串也叫做LCP
    //特别的z[0]=0，也有些题目是等于串长，需要自行调整
    //kmp里面添加字符集外字符的操作在这里也可以用
    int n = str.size();
    std::vector<int> z(n);
    
    for(int i=1,l=0,r=0;i<n;i++){
        if(z[i-l]<r-i+1)
            z[i] = z[i-l];
        else{
            z[i] = std::max(r-i+1,0);
            while(i+z[i]<n && str[z[i]]==str[i+z[i]])
                z[i]++;
            l = i, r = i + z[i] - 1;
        }
    }
    
    return z;
}

//求后缀数组，复杂度O(nlog^2n)
//luogu p3809
int rk[MAXN<<1],sa[MAXN],tarr[MAXN<<1];
//rk[i]表示后缀i（从1开始，后缀i代表字符串从i开始到结束的子串）的排名，sa[i]表示所有后缀第i小的起点序号，排名和编号都从1开始

void getSA(std::string const & s){
    int n = s.size();
    if(n==1){
        rk[1] = sa[1] = 1;
        return;
    }
    
    for(int i=1;i<=n;i++)
        sa[i] = i, rk[i] = s[i-1];
    
    for(int w=1;w<n;w<<=1){
        auto rp = [&](int x){return std::make_pair(rk[x],rk[x+w]);};
        std::sort(sa+1,sa+n+1,[&](int x, int y){return rp(x)<rp(y);});
        for(int i=1,p=0;i<=n;i++)
            tarr[sa[i]] = rp(sa[i-1])==rp(sa[i]) ? p:++p;
        std::copy(tarr+1,tarr+n+1,rk+1);
    }
}

//求后缀数组，复杂度O(nlogn)
//luogu p3809
int rk[MAXN<<1],sa[MAXN],tarr[MAXN<<1],cnt[MAXN],rkt[MAXN];
//rk[i]表示后缀i（从1开始，后缀i代表字符串从i开始到结束的子串）的排名，sa[i]表示所有后缀第i小的起点序号，排名和编号都从1开始

void getSA(std::string const & s){
    int n = s.size();
    if(n==1){
        rk[1] = sa[1] = 1;
        return;
    }
    
    int m = 128;
    for(int i=1;i<=n;i++)
        ++cnt[rk[i]=s[i-1]];
    for(int i=1;i<=m;i++)
        cnt[i] += cnt[i-1];
    for(int i=n;i>=1;i--)
        sa[cnt[rk[i]]--] = i;
    
    for(int w=1;;w<<=1){
        for(int i=n;i>n-w;i--)
            tarr[n-i+1] = i;
        for(int i=1,p=w;i<=n;i++)
            if(sa[i]>w) tarr[++p]=sa[i]-w;
        std::fill(cnt+1,cnt+m+1,0);
        for(int i=1;i<=n;i++)
            cnt[rkt[i] = rk[tarr[i]]]++;
        for(int i=1;i<=m;i++)
            cnt[i]+=cnt[i-1];
        for(int i=n;i>=1;i--)
            sa[cnt[rkt[i]]--] = tarr[i];
        m = 0;
        auto rp = [&](int x){return std::make_pair(rk[x],rk[x+w]);};
        for(int i=1;i<=n;i++)
            tarr[sa[i]] = rp(sa[i-1])==rp(sa[i]) ? m:++m;
        std::copy(tarr+1,tarr+n+1,rk+1);
        if(n==m) break;
    }
}

//后缀自动机，构建SAM的复杂度为O(n)，空间复杂度为O(|S|n)，|S|为字符集的大小
//luogu p3804
//SAM是动态构建的，每次插入一个字符即可
struct State{
    int fa,len,next[26];//似乎有些编译器next是保留字，需要注意
};
//endpos(p)为模式串p在s中所有出现的结束位置的集合，例如aababc中，ab出现了两次，结束位置是{3,5}。endpos等价类即，endpos相同的子串构成的集合。例如b和ab都是结束在{3,5}，则它们是等价类。这说明它们总是一起出现，可以归到一个节点，并且长度小的一定是长度大的的后缀。
//next[ch]表示接受ch后的状态；fa表示该状态在parent tree上的父节点；len表示该状态对应的endpos等价类中最长串的长度。
//假设b是a的fa，a等价类的最长字符串为s，则b的最长字符串为，s的所有后缀中，不在等价类a里的，最长的字符串。

//SAM可以接受字符串的所有后缀，但是它包含了所有子串的信息。也就是从任意一个状态开始的路径，都是字符串的子串。
//可行状态是last状态，以及fa[last]、fa[fa[last]]直到根节点（空字符串）。

//除了等价类的最长字符串长度len，我们也可以计算minlen。等价类里所有字符串的长度恰好覆盖[minlen,len]之间的每一个整数。除了根节点，st[i].minlen = st[fa[i]].len+1;
//每个状态i对应的子串数量是st[i].len-st[st[i].fa].len

//算法并没有维护endpos等效类中，字符串出现的位置个数，需要自己去树形dp。
//注意，aababb中，ab的等价类为{3,5}，根据ab前面一个字符不同可以划分不同的等价类，例如aab和bab划分为{3},{5}。但是a的等价类为{1,2,4}，因为第一个的前面一个字符是空字符，只能划分出两个，即aa{2},ba{4}，树形DP需要在parent tree上注意缺少的这一部分。在建SAM时预处理dp[cur] = 1

class SAM{
public:
    State st[MAXN<<1];//SAM总状态数不会超过2n-1，总转移数不超过3n-4
    int cnt = 1, last = 1;
    //起始节点编号为1；last表示加入新字符前整个字符串所在的等价类
    
    void insert(int ch){
        ch = ch-'a';
        int cur = ++cnt;
        int p = 0;
        st[cur].len = st[last].len + 1;
        for(p=last;p&&!st[p].next[ch];p=st[p].fa)
            st[p].next[ch] = cur;
        //对于每一个father状态，如果不存在ch的转移边，则连到cur
        int q = st[p].next[ch];
        if(q==0){
            //加入了从未加入的字符
            st[cur].fa = 1;
        }
        else if(st[p].len + 1 == st[q].len){
            //p到q是连续的转移
            st[cur].fa = q;
        }
        else{
            //不连续的转移
            //会新增一个节点r,拥有q的所有出边，father与q相同
            int r = ++cnt;
            st[r] = st[q];
            st[r].len = st[p].len + 1;
            for(;p&&st[p].next[ch]==q;p=st[p].fa){
                st[p].next[ch]=r;
            }
            st[cur].fa = st[q].fa = r;
        }
        last = cur;
    }
};

SAM sam;

//广义后缀自动机，其实就是插入多个字符串的后缀自动机，但只能离线build
//luogu p6139
//后缀自动机的性质都可以用过来
struct State{
    int fa,len,next[26];//似乎有些编译器next是保留字，需要注意
};

class GSA{
public:
    State st[MAXN<<1];
    int cnt = 1;//起始节点编号为1
    
    int insert(int last, int ch){
        //传入的是即将插入的字符的父节点编号，以及该字符
        //只用在build里，不要直接把字符串插入，应该先insertTrie再build
        int cur = st[last].next[ch];
        int p = 0;
        st[cur].len = st[last].len + 1;
        
        for(p=st[last].fa;p && !st[p].next[ch];p=st[p].fa)
            st[p].next[ch] = cur;
        
        int q = st[p].next[ch];
        if(q==0){
            st[cur].fa = 1;
        }
        else if(st[p].len+1==st[q].len){
            st[cur].fa = q;
        }
        else{
            int r = ++cnt;
            st[r].fa = st[q].fa;
            for(int i=0;i<26;i++)
                if(st[st[q].next[i]].len)
                    st[r].next[i] = st[q].next[i];
            st[r].len = st[p].len+1;
            for(;p && st[p].next[ch]==q;p=st[p].fa)
                st[p].next[ch] = r;
            st[cur].fa = st[q].fa = r;
        }
        return cur;
        //返回插入节点编号
    }
    
    void build(){
        std::queue<pii> qu;
        for(int i=0;i<26;i++){
            if(st[1].next[i]) qu.push({1,i});
        }
        while(!qu.empty()){
            int fa = qu.front().first;
            int ch = qu.front().second;
            qu.pop();
            int p = insert(fa,ch);
            for(int i=0;i<26;i++){
                if(st[p].next[i]) qu.push({p,i});
            }
        }
    }
    
    void insertTrie(std::string const & str){
        int cur = 1;
        for(auto c:str){
            if(!st[cur].next[c-'a']){
                st[cur].next[c-'a']=++cnt;
            }
            cur = st[cur].next[c-'a'];
        }
    }
};

GSA gsa;

int main(){
    int n;
    std::cin>>n;
    
    for(int i=1;i<=n;i++){
        std::string str;
        std::cin>>str;
        gsa.insertTrie(str);
    }
    gsa.build();

    return 0;
}

//回文字动机，复杂度：线性
//luogu p5496
struct State{
    int len, fail, next[26];
};

//PAM的每一个状态代表原字符串的一个回文子串，每一个转移代表从当前状态字符串的前后同时加一个相同字符后的状态。可以接受其所有回文子串。除了奇根都是可行状态（当然不能为空时偶根不可行）
//fail指针指向该状态的最长回文真后缀。例如ayawaya就指向aya。总体和AC自动机的fail转移很像，都是没有ch的转移，则看fail有没有ch的转移，若fail没有则看fail[fail]的，以此类推。
//回文串分为奇长度和偶长度的，所以PAM有奇根和偶根，偶根的fail指向奇根，奇根不可能失配。
//PAM和SAM一样是动态构建的。

class PAM{
public:
    int last,cnt,pos;
    //last代表上个前缀的最长回文后缀的状态
    State st[MAXN];//最多有n+2个状态和n个转移
    std::string str;
    
    void init(std::string const & s){
        last = 1,pos = -1;
        cnt = 2;//起始两个根为1奇根，2偶根，len分别为-1和0
        st[1].len = -1, st[2].len = 0, st[2].fail = 1;
        str = s;
    }
    
    int up(int p){
        while(str[pos-1-st[p].len]!=str[pos])
            p = st[p].fail;
        return p;
    }
    
    void insert(int ch){
        pos++;
        ch = ch-'a';
        int p = up(last);
        int & q = st[p].next[ch];
        if(!q){
            q=++cnt;
            st[q].len = st[p].len+2;
            st[q].fail = p==1 ? 2 : st[up(st[p].fail)].next[ch];
        }
        last = q;
    }
};

PAM pam;

int main(){
    std::string str
	std::cin>>str;
	pam.init(str);
    for(auto c:str){
        pam.insert(c);
    }

    return 0;
}

//序列自动机，复杂度 O(n|S|)
//luogu p5826
//字符集很大时需要用可持久化线段树维护next
struct State{
    int next[26];  
};

//SQA接受字符串的所有子序列（不需要连续，可以为空）

class SQA{
public:
    State st[MAXN];
    
    void build(std::string const & str){
        int nxt[26];
        std::fill(nxt,nxt+26,0);
        int n = str.size();
        
        for(int i=n-1;i>=0;i--){
            nxt[str[i]-'a'] = i+2;//1号节点是起始空节点
            for(int ch=0;ch<26;ch++){
                st[i+1].next[ch] = nxt[ch];
            }
        }
    }
    
    bool query(std::string const & str){
        //查询str是否是子序列（可以不连续）
        int p = 1, n=str.size();
        for(int i=0;i<n;i++){
            p = st[p].next[str[i]-'a'];
            if(p==0) return false;
        }
        
        return true;
    }
};

SQA sqa;

//复杂度 logn
//luogu B3736
//gcd是可重复贡献的，gcd(x,x)=x，可以用st表维护区间gcd
//x*y=gcd(x,y)*lcm(x,y)，lcm是最小公倍数
#include <iostream>

inline int gcd(int a,int b){
    return b==0 ? a : gcd(b, a%b);
}

int main(){
    int x,y,z;
    std::cin>>x>>y>>z;
    std::cout<<gcd(gcd(x,y),z)<<"\n";
    
    return 0;
}

//复杂度 logn
//求解ax+by=c的一组解，c不是gcd(a,b)的倍数则无解
//扩展欧几里得
//luogu P5656
#include <iostream>
#include <cmath>

using LL = long long;

LL exgcd(LL a,LL b,LL& x,LL& y){
    //求出的是ax+by=gcd(a,b)的一组解，等于c的需要转换一下
    if(b==0){
        x = 1;
        y = 0;//此时ax+by=gcd(a,b)中b=0，任何数与0的最大公约数是他本身，所以ax+0y=a，x=1 y=0
        return a;
    }
    LL d = exgcd(b,a%b,y,x);
    y -= (a/b)*x;
    return d;
}

int main(){
    int T;
    std::cin>>T;
    while(T--){
        LL a,b,c;
        std::cin>>a>>b>>c;
        LL x0=0, y0=0;
        LL d = exgcd(a,b,x0,y0);//d=gcd(a,b)
        if(c%d!=0){//c不是gcd(a,b)的倍数则无解
            std::cout<<"-1\n";
            continue;
        }
        LL x1 = x0*c/d, y1 = y0*c/d;//ax+by=gcd(a,b)的一组解转化为ax+by=c的一组解
        //通解的形式为x=x1+s*dx, y=y1-s*dy
        //其中s为任意整数，dx=b/d, dy = a/d;
        LL dx = b/d, dy = a/d;
        LL l = std::ceil((-x1+1.0)/dx);
        LL r = std::floor((y1-1.0)/dy);
        //x>0,y>0时，s的取值为[l,r]中的整数，若l>r，则说明不存在正整数解
        if(l>r){
            std::cout<<x1+l*dx<<" ";//所有解中x的最小正整数值
            std::cout<<y1-r*dy<<"\n";//所有解中y的最小正整数值
        }
        else{
            std::cout<<r-l+1<<" ";//正整数解的个数
            std::cout<<x1+l*dx<<" ";//正整数解中x的最小值
            std::cout<<y1-r*dy<<" ";//正整数解中y的最小值
            std::cout<<x1+r*dx<<" ";//正整数解中x的最大值
            std::cout<<y1-l*dy<<"\n";//正整数解中y的最大值
        }
        
    }
    return 0;
}

//复杂度 n
//欧拉筛, luogu p3383

int const MAXN = 1e8+5;

std::vector<int> prime;
bool isnp[MAXN];

void sieve(int n){
    isnp[1] = 1;
    isnp[0] = 1;
    for(int i=2;i<=n;i++){
        if(!isnp[i]) prime.push_back(i);
        for(auto p:prime){
            if(i*p>n) break;
            isnp[i*p] = 1;
            if(i%p==0) break;
        }
    }
}

//对数 n 进行 k 轮测试的时间复杂度是 klog^3(n)
//miller-rabin
//loj 143
//通过测试的有可能是素数，不通过的一定不是素数
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstdint>

using LL = __int128;//本题数据范围过大，防止运算中爆掉

LL const test_time = 10;

LL qPowMod(LL n, LL p, LL m){
    LL res = 1;
    while(p>0){
        if(p&1){
            res = (res * n)%m;
        }
        n = (n*n)%m;
        p>>=1;
    }
    return res;
}

bool millerRabin(LL n) {
    if (n < 3 || n % 2 == 0) return n == 2;
    LL a = n - 1, b = 0;
    while (a % 2 == 0) a /= 2, ++b;
    // test_time 为测试次数,建议设为不小于 8
    // 的整数以保证正确率,但也不宜过大,否则会影响效率
    for (LL i = 1, j; i <= test_time; ++i) {
        LL x = rand() % (n - 2) + 2;
        LL v = qPowMod(x, a, n);
        if (v == 1) continue;
        for (j = 0; j < b; ++j) {
            if (v == n - 1) break;
            v = v * v % n;
        }
        if (j == b) return 0;
    }
    return 1;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    srand(time(NULL));
    long long n;
    while(std::cin>>n){
        if(millerRabin(n)){
            std::cout<<"Y\n";
        }
        else{
            std::cout<<"N\n";
        }
    }
    return 0;
}

//复杂度 扩展欧几里得法和费马小定理法都是logn
//乘法逆元
//ax≡1(mod b)，x为a在乘法意义上的逆元，记作a^(-1)，或者inv(a)
//用扩展欧几里得法的角度看，就是求ax+by=1的整数解
//快速幂法利用费马小定理，需要b为素数，并且疑似比exgcd常数大
//luogu P3811，会TLE，需要线性求逆元
//但loj 110不会TLE

int exgcd(int a,int b,int& x,int& y){
    if(b==0){
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b,a%b,y,x);
    y -= (a/b)*x;
    return d;
}

int exgcd_inv(int a, int b){
    //a在模b意义下的逆元
    int x,y;
    int d = exgcd(a,b,x,y);
    if(d!=1){//显然a，b要互质才会有逆元
        return -1;
    }
    else{
        return (x+b)%b;//实际上是为了防止出现x为负数的情况
    }
}

int qPowMod(int x, int p, int mod){
    //x^p % m
    int ans = 1;
    while(p){
        if(p&1){
            ans = (ans*x)%mod;
        }
        x = (x*x)%mod;
        p>>=1;
    }
    return ans;
}

int fermat_inv(int a, int b){//a在模b意义下的逆元
    return qPowMod(a,b-2,b);
}

//线性求逆元，对于1~n这些数，复杂度总共n
//luogu p3381, loj 110
#include <iostream>

using LL = long long;

int const MAXN = 3000005;
LL inv[MAXN];

void getinv(LL n, LL m){
    //求1~n中，每个数在模m意义下的乘法逆元
    inv[1] = 1;
    for(LL i=2;i<=n;i++){
        //inv[i] = -(b/i)*inv[b%i]; //这样写会出现负数
        inv[i] = (LL)(m-m/i)*inv[m%i]%m;
    }
}

//复杂度 logn
//ax≡c (mod b)求解x
//和ax+by=c等价
//luogu p1082
#include <iostream>

using namespace std;

int exgcd(int a,int b,int& x,int& y){
    if(b==0){
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b,a%b,y,x);
    y -= (a/b)*x;
    return d;
}

int linearEquation(int a, int b, int c, int &x, int &y){
    int d = exgcd(a,b,x,y);
    if(c%d!=0) return -1;
    x = x*c/d;
    y = y*c/d;

    return d;
}

int main(){
    int a,b,c,x,y;

    cin>>a>>b;
    c=1;

    int d = linearEquation(a,b,c,x,y);
    //d是a,b的最大公约数，如果无解d==-1
    //下面输出的是最小整数解
    int t = b/d;
    x = (x%t+t)%t;
    cout<<x<<endl;

    return 0;
}

//中国剩余定理 复杂度 klogk
//luogu p1495
typedef long long ll;

const int MAXN = 10005;

ll exgcd(ll a, ll b, ll &x, ll &y){
    if(!b){
        x=1;
        y=0;
        return a;
    }
    ll d = exgcd(b,a%b,x,y);
    ll tmp = x;
    x = y;
    y = tmp - (a/b)*y;
    return d;
}

ll exgcd_inv(ll a, ll b){
    ll x,y;
    ll d = exgcd(a,b,x,y);
    return (x+b)%b;
}

class CRT{
public:
    ll ax[MAXN],rx[MAXN];//每个方程的形式为x≡ai(mod ri)，要求ri互质
    int k=0;//k个方程
    
    void add(ll a, ll r){
        ax[++k] = a;
        rx[k] = r;
    }
    
    ll solve(){
        ll n=1, ans=0;
        for(int i=1;i<=k;i++){
            n = n * rx[i];
        }
        for(int i=1;i<=k;i++){
            ll m = n/rx[i];
            ans = (ans+ax[i]*m*exgcd_inv(m,rx[i]))%n;
        }
        
        return ans;
    }
};

CRT crt;

//复杂度 根号n
int phi(int n){
    int ans = n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            ans = ans/i*(i-1);
            while(n%i==0) n/=i;
        }
    }
    if(n>1) ans = ans/n*(n-1);
    return ans;
}

//求1-N的所有欧拉函数值，使用筛法，埃氏筛复杂度NloglogN，线性筛复杂度N，这里是线性筛
std::vector<int> prime;
bool isnp[MAXN];
int phi[MAXN];

void euler(int n){
    phi[1] = 1;
    for(int i=2;i<=n;i++){
        if(!isnp[i]){
            prime.push_back(i);
            phi[i] = i-1;
        }
        for(auto p:prime){
            if(i*p>n) break;
            isnp[i*p] = 1;
            
            if(i%p==0){
                phi[i*p] = phi[i] * p;
                break;
            }
            else{
                phi[i*p] = phi[i] * phi[p];
            }
        }
    }
}

//线性筛求莫比乌斯函数，复杂度n
int mu[MAXN];
std::vector<int> prime;
bool isnp[MAXN];

void mobius(int n){
    mu[1] = 1;
    for(int i=2;i<=n;i++){
        if(!isnp[i]){
            prime.push_back(i);
            mu[i] = -1;
        }
        
        for(auto p:prime){
            if(i*p>n) break;
            isnp[i*p] = 1;
            if(i%p==0){
                mu[i*p] = 0;
                break;
            }
            else{
                mu[i*p] = mu[i] * mu[p];
            }
        }
    }
}

//UVA 11526
//数论分块模板 复杂度sqrt n
//要求计算i=1~n, ans = ans+n/i
void solve(){
    LL n;
    std::cin>>n;
    LL ans = 0;
    
    LL l = 1, r = 0;
    
    while(l<=n){
        r = n/(n/l);
        ans += (r-l+1) * (n/l);
        l = r+1;  
    }
    std::cout<<ans<<"\n";
}

//杜教筛 复杂度n^(2/3)
//luogu p4213
int const MAXN = 2000005;

int mu[MAXN];
LL phi[MAXN];
std::vector<int> prime;
bool isnp[MAXN];
LL sum_mu[MAXN],sum_phi[MAXN];
std::unordered_map<LL,LL> mp_mu,mp_phi;

void sieve(int n=MAXN-1){
    mu[1] = 1;
    phi[1] = 1;
    for(int i=2;i<=n;i++){
        if(!isnp[i]){
            prime.push_back(i);
            mu[i] = -1;
            phi[i] = i-1;
        }
        
        for(auto p:prime){
            if(i*p>n) break;
            isnp[i*p] = 1;
            if(i%p==0){
                mu[i*p] = 0;
                phi[i*p] = phi[i] * p;
                break;
            }
            else{
                mu[i*p] = mu[i] * mu[p];
                phi[i*p] = phi[i] * phi[p];
            }
        }
    }
    for(int i=1;i<=n;i++){
        sum_mu[i] = sum_mu[i-1]+mu[i];
        sum_phi[i] = sum_phi[i-1]+phi[i];
    }
}

LL sum1(LL n){
    if(n<MAXN){
        return sum_phi[n];
    }
    if(mp_phi.count(n)){
        return mp_phi[n];
    }
    LL l=2, r=0;
    LL ret = n*(1+n)/2;
    while(l<=n){
        r = n/(n/l);
        ret -= (r-l+1)*sum1(n/l);
        l = r+1;
    }
    mp_phi[n] = ret;
    return ret;
}

LL sum2(LL n){
    if(n<MAXN){
        return sum_mu[n];
    }
    if(mp_mu.count(n)){
        return mp_mu[n];
    }
    LL l=2, r=0;
    LL ret = 1;
    while(l<=n){
        r = n/(n/l);
        ret -= (r-l+1)*sum2(n/l);
        l = r+1;
    }
    mp_mu[n] = ret;
    return ret;
}

void solve(){
    LL n;
    std::cin>>n;
    std::cout<<sum1(n)<<" "<<sum2(n)<<"\n";
    
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    sieve();

	int T;
	std::cin>>T;
	//T=1;
	while(T--){
	    solve();
	}

    return 0;
}

int graph[MAXN][MAXN];
//加边删边、访问很方便，a->b，权值为w，则graph[a][b]=w
//空间占用大，并且不能存重边

struct Edge{
    int v,w;//下一点，权
};

std::vector<Edge> edges[MAXN];

//加边u->v,权值w
edges[u].push_back(w);
//访问只能遍历u所连的出边
for(auto x:edges[u]){
    std::cout<<x.v<<" "<<x.w<<"\n";
}

//缺点是，删边难，以及清空边复杂度过高。快速清边见链式前向星传统数组版

struct Edge{
    int v;LL w;//指向的点，容量
    Edge(int v_, LL w_):v(v_),w(w_){}
};

std::vector<Edge> edges;
std::vector<std::vector<int> > graph(MAXN);
//常用于网络流，例如加u->v，权值为w，及其反向边v->w，权值为0
graph[u].push_back(edges.size());
edges.push_back(Edge(v,w));
graph[v].push_back(edges.size());
edges.push_back(Edge(u,0));
//遍历u的边时
for(auto x:graph[u]){
    auto e=edges[x];
    auto v=e.v, w=e.w;
    //e的反向边就是edges[x^1]
}

//清空某个点连出的所有边时，graph[u].clear()，不需要管edges的size
//清除整个图时edges.clear()，graph要对每个下标clear
//这种清除方式复杂度比传统数组版高很多，需要反复建图时不推荐使用。
//好处是不需要让边编号从2开始，从0开始即可存反向边

struct Edge{
    int v,w,next;//指向的点，边权，下一条边
};

Edge edges[MAXM];//存无向图记得开两倍
int head[MAXN],cnt;//如果要存反向边，并且用^1取反向边，应初始化cnt=1
//不应把后面add的逻辑改成最后再cnt++，因为我们遍历边的时候是判断e是否等于0，所以不应该有边的编号等于0

inline void add(int u, int v, int w){
    edges[++cnt].w = w;
    edges[cnt].v = v;
    edges[cnt].next = head[u];//把下一条边设置为当前起点的第一条边
    head[u] = cnt;//该边称为当前起点的第一条边
}

//遍历，与vector版不同，vector版按加入先后顺序遍历，而这里是反向顺序遍历。绝大多数情况不影响
//例如遍历1号节点所连的边
for(int e=head[1];e;e=edges[e].next){
    std::cout<<edges[e].v<<" "<<edges[e].w<<"\n";
}

//当需要清空某个点的所有连出边时, head[u] = 0，不需要管cnt
//清空全图时，cnt = 0, 对于所有点head = 0， 由于还可以用memset，比vector版更是快了不少

//复杂度 优先队列实现为mlogm
//dijkstra，单源最短路
//luogu p4779
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#define MAXN 500005
#define MAXINT 0x7fffffff

struct Edge{
    int v,w;//下一点，权
    Edge(int v_, int w_):v(v_),w(w_){}
};

struct Node {
    int dis, u;//存储起点到u点的距离
    Node(int dis_, int u_):dis(dis_),u(u_){};
    bool operator>(Node const & a) const { return dis > a.dis; }
};

std::vector<Edge> graph[MAXN];
int dis[MAXN];
bool tag[MAXN];

std::priority_queue<Node, std::vector<Node>, std::greater<Node> > pq;

void init(int n){
    for(int i=1;i<=n;i++){
        dis[i] = MAXINT;
        //初始化为无限远
        tag[i] = 0;
        graph[i].clear();
    }
    while(!pq.empty()) pq.pop();
}

void dijk(int s){
    dis[s]=0;
    pq.push(Node(0,s));

    while (!pq.empty())
    {
        int u = pq.top().u;
        pq.pop();
        if(tag[u]) continue;
        tag[u]=1;
        for(auto g : graph[u]){
            int v = g.v, w = g.w;
            if(dis[v]>dis[u]+w){
                dis[v] = dis[u]+w;
                pq.push(Node(dis[v],v));
            }
        }
    }
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n,m,s;
    std::cin>>n>>m>>s;
    //点数，边数，起点
    init(n);

    for(int i=1;i<=m;i++){
        int u,v,w;
        std::cin>>u>>v>>w;//起点，终点，边权
        graph[u].push_back(Edge(v,w));
    }
    dijk(s);

    for(int i=1;i<=n;i++){
        std::cout<<dis[i]<<" ";
    }
    return 0;
}

//复杂度 nm
//bellman-ford, 单源最短路
//luogu p4779，有一个点TLE
#include <iostream>
#include <vector>
#include <cstring>

int const MAXN = 100005;
int const INF = 0x6fffffff;

struct Edge{
    int v,w;//下一点,权
    Edge(int v_, int w_):v(v_),w(w_){}
};

int dis[MAXN];
std::vector<Edge> graph[MAXN];

void init(int n){
    for(int i=1;i<=n;i++){
        dis[i]=INF;
        graph[i].clear();
    }
}

bool BF(int n, int s){
    //如果不存在最短路就返回0，否则返回1
    dis[s] = 0;
    bool flag = 1;
    for (int i=1;i<=n;i++){//松弛n-1轮，若第n轮还能松弛，就说明有负环
        flag = 1;
        for(int u=1;u<=n;u++){//这里看似是两层循环，实际上总数是边数，整个算法的复杂度是mn
            for (auto e : graph[u]){
                int w=e.w,v=e.v;
                if(dis[v]>dis[u]+w){
                    dis[v]=dis[u]+w;
                    flag = 0;
                }
            }
        }
        if(flag){
            break;
        }
    }
    
    return flag;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n,m,s;//点数，边数，起点
    std::cin>>n>>m>>s;
    init(n);

    for(int i=1;i<=m;i++){
        int u,v,w;
        std::cin>>u>>v>>w;
        //起点，终点，边权
        graph[u].push_back(Edge(v,w));
    }
    
    BF(n,s);

    for(int i=1;i<=n;i++){
        std::cout<<dis[i]<<" ";
    }
    
    return 0;
}

//复杂度 nm
/*
    bellman-ford的优化
    只有上一次被松弛的结点，所连接的边，
    才有可能引起下一次的松弛操作
*/
//spfa 单源最短路
//luogu P3371
#include <iostream>
#include <vector>
#include <queue>

int const MAXN = 100005;
int const INF = 0x5fffffff;

struct Edge{
    int v,w;
    Edge(int v_, int w_):v(v_),w(w_){}
};

int dis[MAXN];//距离
int cnt[MAXN];//算到达本节点所要经过的边数，若cnt>=n，则说明有负权环
bool tag[MAXN];//用于判断是否为上次松弛过的节点的边所连的点

std::queue<int> qu;
std::vector<Edge> graph[MAXN];

void init(int n){
    while(!qu.empty()) qu.pop();
    for(int i=1;i<=n;i++){
        dis[i] = INF;
        cnt[i] = 0;
        tag[i] = 0;
        graph[i].clear();
    }
}

bool SPFA(int n, int s){
    //如果不存在最短路就返回0，否则返回1
    dis[s] = 0;
    tag[s] = 1;
    qu.push(s);
    bool flag = 1;

    while(!qu.empty()){
        if(!flag) break;
        int u = qu.front();
        qu.pop();
        tag[u]=0;
        for(auto e : graph[u]){
            int v = e.v, w = e.w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n) {
                    flag = 0;
                    break;
                }
                if(!tag[v]){
                    qu.push(v);
                    tag[v]=1;
                }
            }
        }
    }
    return flag;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n,m,s;
    std::cin>>n>>m>>s;
    init(n);

    for(int i=1;i<=m;i++){
        int u,v,w;
        std::cin>>u>>v>>w;
        //起点，终点，边权
        graph[u].push_back(Edge(v,w));
    }

    SPFA(n,s);
    for(int i=1;i<=n;i++){
        if(dis[i]!=INF){
            std::cout<<dis[i]<<" ";
        }
        else{
            std::cout<<"2147483647 ";//根据luogu P3371要输出这个数
        }
    }

    return 0;
}

//复杂度 n^3
//floyd全源最短路
//luogu p5905，由于不能判断负环和速度慢，会wa和tle一些
//floyd虽然不能处理负环但是可以接受负边
#include <iostream>
#include <cstring>

using LL = long long;

int const MAXN = 3005;
LL const INF = 1e17; //不能设置为int的最大值，否则后面加法可能导致溢出
LL graph[MAXN][MAXN];

int main(){
    int n,m;//点数，边数
    std::cin>>n>>m;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            graph[i][j] = INF;
        }
    }
    for(int i=1;i<=m;i++){
        int u,v;LL w;
        std::cin>>u>>v>>w;//起点，终点，边权
        graph[u][v] = std::min(graph[u][v], w);//处理重边
    }
    for(int i = 1;i<=n;i++){
        graph[i][i] = 0;
    }

    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                graph[i][j] = std::min(graph[i][j],graph[i][k]+graph[k][j]);
            }
        }
    }
    
    for(int i=1;i<=n;i++){
        LL res=0;
        for(LL j=1;j<=n;j++){
            if(graph[i][j]>1e9) graph[i][j] = 1e9;
            res += j*graph[i][j];
        }
        std::cout<<res<<"\n";
    }

    return 0;
}

//差分约束，复杂度同SPFA
//luogu p5960
//使用介绍见markdown
#include <iostream>
#include <vector>
#include <queue>

int const MAXN = 5005;
int const INF = 0x5fffffff;

struct Edge{
    int v,w;
    Edge(int v_, int w_):v(v_),w(w_){}
};

int dis[MAXN];//距离
int cnt[MAXN];//算到达本节点所要经过的边数，若cnt>=n，则说明有负权环
bool tag[MAXN];//用于判断是否为上次松弛过的节点的边所连的点

std::queue<int> qu;
std::vector<Edge> graph[MAXN];

void init(int n){
    while(!qu.empty()) qu.pop();
    for(int i=1;i<=n;i++){
        dis[i] = INF;
        cnt[i] = 0;
        tag[i] = 0;
        graph[i].clear();
    }
}

bool SPFA(int n, int s){
    //如果不存在最短路就返回0，否则返回1
    dis[s] = 0;
    tag[s] = 1;
    qu.push(s);
    bool flag = 1;

    while(!qu.empty()){
        if(!flag) break;
        int u = qu.front();
        qu.pop();
        tag[u]=0;
        for(auto e : graph[u]){
            int v = e.v, w = e.w;
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n) {
                    flag = 0;
                    break;
                }
                if(!tag[v]){
                    qu.push(v);
                    tag[v]=1;
                }
            }
        }
    }
    return flag;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int n,m;
    std::cin>>n>>m;
    init(n+1);
    
    for(int i=1;i<=m;i++){
        int v,u,w;
        std::cin>>v>>u>>w;
        graph[u].push_back(Edge(v,w));
    }
    for(int i=1;i<=n;i++){
        graph[n+1].push_back(Edge(i,0));
    }
    n++;
    
    if(!SPFA(n,n)){
        std::cout<<"NO\n";
        return 0;
    }
    for(int i=1;i<=n-1;i++){
        std::cout<<dis[i]<<" ";
    }
    

    return 0;
}

//复杂度 n
//拓扑排序, luogu B3644
#include <iostream>
#include <vector>
#include <queue>

int const MAXN = 105;

std::vector<int> graph[MAXN];
int in[MAXN];

int main(){
    int n;
    std::cin>>n;

    for(int i=1;i<=n;i++){
        while(true){
            int v;
            std::cin>>v;
            if(v==0) break;
            graph[i].push_back(v);
            in[v]++;
        }
    }
    
    std::queue<int> qu;
    for(int i=1;i<=n;i++){
        if(in[i]==0) qu.push(i);
    }
    
    while(!qu.empty()){
        int u = qu.front();
        qu.pop();
        std::cout<<u<<" ";
        for(auto v:graph[u]){
            in[v]--;
            if(in[v]==0) qu.push(v);
        }
    }

    return 0;
}

//复杂度 mlogm
//最小生成树Kruskal，luogu p3366
#include <iostream>
#include <algorithm>

int const MAXM = 200005;
int const MAXN = 5005;

struct Edge{
    int u,v,w;//最小生成树是在无向图上跑的，由于要排序，所以记录uvw
    bool operator<(Edge const & x) const {
        return w<x.w;
    }  
};

Edge edges[MAXM];
int find_sets[MAXN];//并查集

int find(int x){return find_sets[x]==x ? x : find_sets[x] = find(find_sets[x]);}

int main(){
    int n,m;//点数和边数

    std::cin>>n>>m;
    for(int i=1;i<=m;i++){
        std::cin>>edges[i].u>>edges[i].v>>edges[i].w;
    }
    std::sort(edges+1,edges+1+m);

    for(int i=1;i<=n;i++){
        find_sets[i]=i;
    }

    int ans = 0;
    int cnt=0;

    for(int i=1;i<=m;i++){
        int u = edges[i].u, v = edges[i].v;
        int x = find(u);
        int y = find(v);

        if(x!=y){
            ans += edges[i].w;
            find_sets[x] = y;
            cnt++;
        }
    }
    //计数，如果小于n-1则不连通
    
    if(cnt<n-1){
        std::cout<<"orz\n";
    }
    else{
        std::cout<<ans<<"\n";
    }

    return 0;
}

//复杂度 (m+n)logn
//最小生成树prim，luogu p3366
#include <iostream>
#include <vector>
#include <queue>

const int MAXN = 5005;
const int MAXM = 200005;
const int INF = 0x5fffffff;

struct edge{
    int v,w;

    edge(){};
    edge(int v,int w):v(v),w(w){}

    bool operator>(const edge& x) const {return w>x.w;}
};

std::vector<edge> graph[MAXN];
bool vis[MAXN];

std::priority_queue<edge, std::vector<edge>, std::greater<edge> > pq;

int main(){
    int n,m;//点数，边数
    std::cin>>n>>m;
    int ans = 0;
    int cnt = 1;

    for(int i=1;i<=m;i++){
        int u,v,w;//起点，终点，边权
        std::cin>>u>>v>>w;
        graph[u].push_back(edge(v,w));
        graph[v].push_back(edge(u,w));
        //无向图
    }

    for(int i=0;i<graph[1].size();i++){
        pq.push(graph[1][i]);
    }
    vis[1]=true;

    while(cnt!=n&&!pq.empty()){
        edge minx=pq.top();
        pq.pop();
        while(vis[minx.v]){
            if(pq.empty()){
                std::cout<<"orz\n";//不连通
                return 0;
            }
            minx=pq.top();
            pq.pop();
        }
        
        vis[minx.v] = true;
        ans+=minx.w;
        cnt++;
        
        for(int i=0;i<graph[minx.v].size();i++){
            if(!vis[graph[minx.v][i].v])
                pq.push(graph[minx.v][i]);
        }
    }

    if(cnt<n){
        std::cout<<"orz\n";
    }
    else{
        std::cout<<ans<<"\n";
    }

    return 0;
}

//复杂度 nm
//最小树形图，朱刘算法
//从根节点能到达其他所有点
//luogu4716
#include <iostream>

const int MAXN = 105;
const int MAXM = 10005;
const int INF = 0x7fffffff;

struct Edge{
    int u,v,w;
};

Edge edge[MAXM]; 
int vis[MAXN],id[MAXN];
int in[MAXN],pre[MAXN];

int zhuliu(int n, int m, int root){
    //返回最小树形图的边权和，如果不存在则返回-1
    int ans = 0;
    for(;;){
        for(int i=1;i<=n;i++) in[i]=INF;
        
        for(int i=1;i<=m;i++){
            int u = edge[i].u;
            int v = edge[i].v;
            if(u!=v && edge[i].w<in[v]){//遍历所有边，找到对每个点的最短入边
                in[v] = edge[i].w;
                pre[v] = u;
            }
        }
        
        for(int i=1;i<=n;i++){
            if(i!=root && in[i]==INF){
                return -1;//无解
            }
        }
        
        int cnt = 0;//记录环数以及下一次循环的点数
        
        for(int i=1;i<=n;i++){
            vis[i] = -1;
            id[i] = -1;
        }
        
        in[root] = 0;
        
        for(int i=1;i<=n;i++){
            if(i==root) continue;
            ans += in[i];
            int v=i;
            while(vis[v]!=i&&id[v]==-1&&v!=root){
                vis[v] = i;
                v = pre[v];
            }
            if(v!=root && id[v]==-1){
                id[v] = ++cnt;
                for(int u=pre[v];u!=v;u=pre[u]) id[u] = cnt;
            }
        }
        
        if(cnt==0){//无环，得到解
            break;
        }
        
        for(int i=1;i<=n;i++){
            if(id[i]==-1) id[i]=++cnt;
        }
        
        for(int i=1;i<=m;i++){
            int u = edge[i].u;
            int v = edge[i].v;
            edge[i].u = id[u];
            edge[i].v = id[v];
            if(edge[i].u!=edge[i].v) edge[i].w -= in[v];
        }
        
        n = cnt;
        root = id[root];
    }
    return ans;
}

int main(){
    int n,m,root;
    std::cin>>n>>m>>root;
    //点数，边数，根节点序号
    for(int i=1;i<=m;i++){
        std::cin>>edge[i].u>>edge[i].v>>edge[i].w;
        //起点，终点，边权
    }
    std::cout<<zhuliu(n,m,root)<<"\n";
    return 0;
}

//复杂度 nm
//luogu p3386
//求二分图最大匹配，根据定理，最大匹配=最小点覆盖，以及最小边覆盖=点数-最大匹配

//二分图是"可以将点集分为两个不相交的部分，所有边连接的两个顶点在不同的部分中"的图

//二分图的匹配：边集的任意子集的任意两条边都没有公共顶点，则这个子集是一个匹配
//二分图的最大匹配：所有匹配中边数最多的
//最小点覆盖：选最少的点，满足每条边至少有一个端点被选
//最大独立集：选最多的点，满足两两之间没有边相连
//这里的二分图是无向图
//如果最大匹配中所有点都被匹配，那么叫做完美匹配

#include <iostream>
#include <cstring>

const int MAXN = 505;
bool graph[MAXN][MAXN];
bool vis[MAXN];
int toLeft[MAXN];//标记右边节点i连到了哪个左边界点，即toLeft[i]

bool match(int const & i, int const & rightNum){
    for(int j=1;j<=rightNum;j++){
        if(graph[i][j]&&!vis[j]){
            vis[j] = true;
            if(toLeft[j]==0 || match(toLeft[j], rightNum)){
                toLeft[j] = i;
                return true;
            }
        }
    }
    return false;
}

int hungarian(int const & leftNum, int const & rightNum){
    //返回最大的边数
    int cnt = 0;

    for(int i=1;i<=leftNum;i++){
        std::memset(vis,0,sizeof(vis));
        if(match(i,rightNum)) cnt++;
    }

    return cnt;
}

int main(){
    int n,m,e;//左边点数，右边点数，边数
    std::cin>>n>>m>>e;
    
    for(int i=1;i<=e;i++){
        int x,y;
        std::cin>>x>>y;
        graph[x][y] = true;
    }

    std::cout<<hungarian(n,m)<<"\n";

    return 0;
}