char* intToRoman(int n) {
    const int num[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    char chrs[][3] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
    int idx = 0, i = 0;
    char * str = malloc(sizeof(char) * 32);
    while(n)
    {
        while(n < num[i]) i++;
        n -= num[i];
        str[idx++] = chrs[i][0];
        if(i & 1)
            str[idx++] = chrs[i][1];
    }
    str[idx] = 0;
    return str;
}