Coprime
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
Background
wly09：“我喜欢你，跟我交往吧”
这是一道提交答案题。
Description
你加入了一个神秘的秘密社团。
由于这个社团很神秘，这个社团拥有一个神秘的密码系统。
由于这个密码系统很神秘，密码系统使用一个神秘的圆形密码盘，密码盘上排列着 共 个数字，密码盘可以旋转（换句话说，这是个 的圆排列）。
由于这个圆形密码盘很神秘，圆形密码盘上任意两个相邻数字必须互质。
对于所有 ，你想知道满足规则的密码盘的数量，由于这个数可能很大，你只需输出它模 的结果。
Constraints and Subtasks
本题只有一个测试点，保证 。
你可能不能计算所有询问的答案，假设你正确计算出 个，则你的分数是本题满分的 倍，具体地：
$$S(Q)=\log_{\frac{N}{117}+1}\left(\dfrac{Q}{117}+1\right) $$Output
你需要提交一个含有 行数字的文件，第 行表示 时问题的答案。
注意即使你不会某个问题，为了得到其他问题的分数，你有必要填写一个 32 位有符号整数确保输出格式正确。
Samples
1
1
2
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
在样例输入中， 的回答是正确的。
