Mẹ nhờ em đong dầu.

Coi như số lượng dầu mẹ em đang có là vô hạn. Em cần đong \(n\) lít dầu vào can dầu lớn, tuy nhiên trong nhà chỉ có 2 loại can là loại can \(2\) lít và can \(3\) lít. Vì nhà giàu nên em muốn bao nhiêu can thuộc 2 loại trên đều có đủ. Em có thể thực hiện các thao tác sau:

• Múc đầy một can \(2\ell\) hoặc \(3\ell\) để đưa thêm dầu từ nguồn vào can lớn
• Múc đầy một can \(2\ell\) hoặc \(3\ell\) để rút bớt dầu từ can lớn về lại nguồn.

Người ta bảo "người lười thường rất thông minh". Em hãy tính xem số thao tác tối thiểu cần phải dùng để đong được đúng \(n\) lít dầu vào can lớn

Input

• Một dòng duy nhất chứa một số nguyên dương \(n\) \((n \le 10^9)\)

Output

• Số lượng can ít nhất em cần dùng để đong được \(n\) lít dầu.

Subtask

• Subtask \(1\) (\(60\%\) số điểm): \(n \le 10^3\)
• Subtask \(2\) (\(40\%\) số điểm): Không có giới hạn gì thêm.

Sample

5

2