// Author: Damian Straszak import java.io.*; import java.util.*; public class D { BufferedReader br; PrintWriter out; StringTokenizer st; boolean eof; long gcd(long a,long b) { if (a==0) return b; return gcd(b%a,a); } void solve() throws IOException { int test=nextInt(); while(test-->0) { int n=nextInt(); long[] x=new long[n]; long[] y=new long[n]; long[] r=new long[n]; int[] move=new int[n]; for(int i=0;i st=new Stack(); st.push(0); move[0]=1; while(!st.empty()) { Integer u=(Integer)st.pop(); for(int i=0;i