配点:200200

問題文

正の整数 nn に対して f(n)f(n) を次のように定めます:
f(n)1kn(kk!)+1\displaystyle f(n) \coloneqq \sum_{1 \leq k \leq n} (k \cdot k!) + 1

正の整数 NN について,f(N)f(N)2p2^p の倍数となるような最大の非負整数 pp を求めてください.

ただし,任意の正の整数 xx に対して x!=1kxk\displaystyle x! = \prod_{1 \leq k \leq x} k を満たします.

制約

  • 1Φ1051 \leq \Phi \leq 10^5
  • 1N2601 \leq N \leq 2^{60}
  • 入力はすべて整数

入力

各テストケースの入力は,それぞれ以下の形式で与えられる:

NN

出力

答えを出力せよ.

サンプル

入力例1
2
3
1
出力例1
3
1

f(3)=(11!+22!+33!)+1=24=233f(3) = (1 \cdot 1! + 2 \cdot 2! + 3 \cdot 3!) + 1 = 24 = 2^3 \cdot 3 を満たします.

Submit


Go (1.21)