Description

然而，XHY同学并不会做PPT，于是她找到了CYD大神求助。她想把N张4*3的照片不重叠，无缝隙地拼成一个矩形作为背景图片。为了美观，她希望背景图片的长与宽尽可能接近，并且在长宽均相等的情况下，使得旋转的照片张数尽可能少。（4*3的不算旋转，3*4的算作旋转，且照片只能有这两种尺寸）。

请你帮CYD大神写一个程序，帮XHY同学设计一种满足她要求的照片排列方式，使得旋转的照片张数最少。

Input Format

第一行，一个正整数N。

Output Format

仅一行，一个非负整数表示最少的旋转照片张数。

6

0

7

3

Hint

对于20%数据，N<=10。

对于30%数据，N<=20。

对于50%数据，N<=50。

对于70%数据，N<=233。

对于100%数据，N<=900。