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

Input

The first line consists of integer N representing number of test cases.

Next N lines consist of N integers (1 ≤ k ≤ 10¹⁵).

Output

N lines each displaying corresponding k-th amusing number.

Example

Input:
2
1
5
Output:
5
65