Xét số nguyên dương ~X~ và gọi ~S~ là tổng tất cả các ước dương của ~2004^X~.

Cần tính phần dư của ~S~ cho ~29~. Ví dụ, với ~X = 1~, các ước dương của ~2004^1~ là ~1, 2, 3, 4, 6, 12, 167, 334, 501, 668, 1002~ và ~2004~. Do đó ~S = 4704~ và số dư của S chia cho ~29~ là ~6~.

Input

Gồm nhiều bộ test, mỗi bộ là một số nguyên ~X~ ~\left(1 \leq X \leq 10000000\right)~.

Bộ test với ~X = 0~ để kết thúc chương trình và không cần xử lý.

Output

Với mỗi bộ test, in ra một kết quả của số dư ~S~ chia cho ~29~ trên ~1~ dòng.

Sample Input

1 
10000 
0

Sample Output

6
10