import java.io.*;
import java.util.*;
import java.lang.*;
class DPnCr{
public static void main(String[] ss)throws Exception{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter out=new BufferedWriter(new OutputStreamWriter(System.out));
int tests=Integer.parseInt(br.readLine());
for(int t=0;t