Amusing numbers are numbers consisting only of digits 5 and 6. Given an integer k , display the k-th amusing number.

Input

FIrst line consists of integer N representing number of test cases

Next N lines consist of N integers (1 <= k <= 10^15)

Output

N lines each displaying corresponding k-th amusing number

Example

Input:
2
1
5
Output:
5
65