Một số hoàn hảo là một số không vượt quá 100 chỉ gồm các chữ số 4, 6 và 9. Một số được gọi là số đẹp nếu nó chia hết cho ít nhất một số hoàn hảo nào đó. Cho số tự nhiên n (1≤n≤18), tìm số lượng số đẹp không vượt quá 10^n.

Dữ liệu:

-Dòng đầu tiên chứa số nguyên dương T (1≤T≤10) là số lượng bài toán cần giải.

-T dòng tiếp theo,mỗi dòng chứa một số nguyên dương n tương ứng với yêu cầu bài toán (1≤n≤18).

Kết quả:

• Ghi T dòng ứng với T bài toán cần giải

Sample Input

1
1

Sample Output

5