import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.NoSuchElementException; class Main { public static void main(String[] args) { new Main().run(); } void run() { solve(); } long mul(long a, long b, long mod) { if (a > b) { return mul(b, a, mod); } if (b<1e9) return a*b%mod; if (a == 1) return b; //(2k+1)b if (a%2==1) { return (b+mul(a-1,b,mod))%mod; } else { return 2*mul(a/2,b,mod)%mod; } } long powmod(long a, long n, long mod) { if (n==0) return 1; return mul(powmod(mul(a,a,mod), n/2, mod) , (n%2==1 ? a : 1), mod); } void solve() { FastScanner sc=new FastScanner(); PrintWriter pw=new PrintWriter(System.out); int T=sc.nextInt(); for (int i=0;i