Cho số nguyên dương \(X\), biết \(Z\) là số có dạng \(4…440…0\). Tìm \(Z\) nhỏ nhất chia hết cho \(X\) . Chú ý rằng \(Z\) phải có số 4 và có thể không chứa số \(0\) nào.

Đặt \(a\) là số lượng số \(4\) trong \(Z\), \(b\) là số lượng số \(0\) trong \(Z\). Chúng ta cần tính \(2.a+b\).

Input

• Dòng đầu chứa số nguyên \(t\) là số bộ thử.
• \(t\) dòng sau mỗi dòng chứa một số nguyên \(X\).

Output

• Với mỗi bộ thử in ra giá trị \(2.a+b\).

Constraints

• \(0<t\leq 10\)
• \(1\leq X\leq 10^5\)

Example

Sample Input

3
4
5
80

Sample Output

2
3
4