整除座位排列

題目敘述

班上有 n 位學生，學號為 1 到 n，教室也有 n 個座位，座號為 1 到 n。老師要把學生安排入座，用排列 p₁, p₂, …, p_n 表示座號 i 坐的是學號 p_i 的學生。

如果每個座號 i 都滿足「p_i 能整除 i」或「i 能整除 p_i」，這種排法就稱為合格。請計算 1..n 的排列中有多少個合格。

輸入格式

輸入一行，包含一個整數 n。

輸出格式

輸出一個整數，為合格排列的個數。

限制

• 1 ≤ n ≤ 15

範例

範例 1

輸入

2

輸出

2

範例 2

輸入

1

輸出

1

說明

範例 1：兩個排列 [1,2] 與 [2,1] 都合格。

範例 2：只有 [1] 一種。