import java.util.ArrayList; import java.util.Scanner; class Main { public static void main(String[] args) { new Main().run(); } long solve(long A,long B,long C) { if(C==1&&A>1)return -1; long ans=0; while(A>0) { if(C<=A&&A<=2*C-2) { A=0; ans+=B; }else if(A%C!=0) { A-=A%C; }else { A/=C; } ans+=B; } return ans; } void run() { Scanner sc=new Scanner(System.in); int Q=sc.nextInt(); for(int q=0;q