URL Shortener

You have given a URL id – 'N' consisting of only digits. Your task is to generate a short URL for the given URL id.

To generate a short URL, you need to convert the given URL id to 62 base number where digits of the number are:[“0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ”] i.e “0” corresponds to 0, “a” corresponds to 10, “Z” corresponds to 61, and “10” corresponds to 62, “11” corresponds to 63, and so on….

Follow Up:

Can you solve this in logarithmic time and space complexity?

Input format :

The first line of input contains a single integer 'T', representing the number of test cases. 

The first line of each test contains a single integer 'N', denoting the URL id. 

Output format :

For each test case, return a short URL for the URL id.

Note:

You don't need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 1000  
0 <= N <= 10^18 

Time limit: 1sec