Charlie and Johnny play a game. For every integer Charlie gives, Johnny has to find the smallest positive integer such that ( multiplied by ) contains only 4s and 0s and starts with one or more 4s followed by zero or more 0s. For example, 404 is an invalid number but 4400, 440, and 444 are valid numbers.

If is the number of 4s and is the number of 0s, can you print the value of ?

Input Format

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

lines follow, each line containing the integer as stated above.

Output Format

For every , print the output in a newline as stated in the problem statement.

Constraints

Sample Input

3
4
5
80

Sample Output

2
3
4

Explanation

For the 1^st test case, the smallest such multiple of is 4 itself. Hence the value of will be and and the value of will be , and the answer is .

For the 2^nd test case, and 40 is the minimum such multiple of . Hence the values of , and will be , and respectively.