AT_abc403_f [ABC403F] Shortest One Formula

You are given a positive integer $ N $ . Among all valid arithmetic expressions consisting of the characters `1`, `+`, `*`, `(`, and `)`, find one of the minimum length whose value is $ N $ . More formally, among the strings $ S $ satisfying all of the following conditions, find one of the minimum length: - $ S $ conforms to the symbol `` in the [BNF](https://en.wikipedia.org/wiki/Backus%E2%80%93Naur_form) below. - The value of the expression represented by $ S $ is $ N $ . ``` ::= | "+" ::= | "*" ::= | "(" ")" ::= "1" | "1" ``` Strings that conform to `` include: - `1111+111` representing $ 1111+111 $ . - `(1+1)*(1+1)` representing $ (1+1)\times(1+1) $ . - `(11+(1+1)*(1+1))+1` representing $ (11+(1+1)\times(1+1))+1 $ . Strings that do not conform to `` include: - `(1+1)(1+1)` - `1+2` - `1-1` - `1/1` - `)1(` - `1++1` - `+1` - `(+1)` - `1*+1`

The input is given from Standard Input in the following format: > $ N $

Print a solution.

### Sample Explanation 1 Expressions whose value is $ 9 $ include: - `(1+1+1)*(1+1+1)` - `1+1+1+1+1+1+1+1+1` - `(1+1)*(1+1)*(1+1)+1` Among them, a shortest is `(1+1+1)*(1+1+1)`. ### Constraints - $ 1 \le N \le 2000 $ - All input values are integers.