Một bài toán về số học thú vị như sau: "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~ ".

Input

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~).

Output

Gồm ~T~ dòng, mỗi dòng chứa kết quả bài toán ứng với bài toán cần giải.

Sample Test

Input

1
1

Output

5