Integer to words

//Integer to words

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine().trim());

        while(tc-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            String ans = new Solution().convertToWords(n);
            System.out.println("\"" + ans + "\"");
        }
    }
}

class Solution {
    String convertToWords(int n) {
        if(n == 0) {
            return "Zero";
        }

        int[] values = {
            1000000000, 1000000, 1000, 100, 90, 80, 70,
            60, 50, 40, 30, 20, 19, 18, 17, 16, 15, 14,
            13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
        };

        String[] words = {
            "Billion", "Million", "Thousand", "Hundred",
            "Ninety", "Eighty", "Seventy", "Sixty", "Fifty",
            "Forty", "Thirty", "Twenty", "Nineteen",
            "Eighteen", "Seventeen", "Sixteen", "Fifteen",
            "Fourteen", "Thirteen", "Twelve", "Eleven",
            "Ten", "Nine", "Eight", "Seven", "Six", "Five",
            "Four", "Three", "Two", "One"
        };

        return convertToWordsRec(n, values, words);
    }
    
    static String convertToWordsRec(int n, int[] values, String[] words) {
        String res = "";

        for(int i = 0; i < values.length; i++) {
            int value = values[i];
            String word = words[i];

            if(n >= value) {
                if(n >= 100) {
                    res += convertToWordsRec(n / value, values, words) + " ";
                }

                res += word;

                if(n % value > 0) {
                    res += " " + convertToWordsRec(n % value, values, words);
                }

                return res;
            }
        }

        return res;
    }
}