Phúc rất thích số 4, 6 và 9. Chính vì thế anh ta quan niệm các số chỉ gồm các chữ số 4, 6 và 9 là những số hoàn hảo. Anh ấy cho rằng các số chia hết cho những số hoàn hảo này là những số đẹp. Một ngày nọ khi đang trên đường trở về nhà, anh ấy nhìn thấy những con số được ai đó viết lại trên xe buýt. Anh ấy chợt nghĩ ra một bài toán, đếm số lượng những số đẹp không vượt quá ~10^n~ với 1 số tự nhiên n cho trước. Suy đi nghĩ lại anh ấy thấy bài toán này quá khó để giải được với n lớn. Chính vì vậy anh ấy đã nghĩ ra một bài toán mới tương tự nhưng dễ hơn. Anh định nghĩa lại về một số hoàn hảo. 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 vào:

• 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ả:

Đưa ra kết quả bài toán trên T dòng ứng với T bài toán cần giải.

Ví dụ

input

1
1

ouput

5