AT_abc403_f [ABC403F] Shortest One Formula

正整数 $ N $ が与えられます。 `1`, `+`, `*`, `(`, `)` のみからなる数式のうち、値が $ N $ となるものの中で、文字列としての長さが最小のものを一つ求めてください。 より厳密には、以下の条件をすべて満たす文字列 $ S $ のうち長さが最小のものを一つ求めてください。 - $ S $ は下の [BNF 記法](https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%83%E3%82%AB%E3%82%B9%E3%83%BB%E3%83%8A%E3%82%A6%E3%82%A2%E8%A8%98%E6%B3%95) の `` シンボルに従う文字列である。 - $ S $ が表す数式の値は $ N $ である。 ``` ::= | "+" ::= | "*" ::= | "(" ")" ::= "1" | "1" ``` `` シンボルに従う文字列として、以下のようなものがあります。 - `1111+111` : $ 1111+111 $ を表します。 - `(1+1)*(1+1)` : $ (1+1)\times (1+1) $ を表します。 - `(11+(1+1)*(1+1))+1` : $ (11+(1+1)\times (1+1))+1 $ を表します。 一方、以下の文字列は `` シンボルに従いません。 - `(1+1)(1+1)` - `1+2` - `1-1` - `1/1` - `)1(` - `1++1` - `+1` - `(+1)` - `1*+1`

入力は以下の形式で標準入力から与えられる。 > $ N $

答えを出力せよ。

### Sample Explanation 1 値が $ 9 $ となるような数式は例えば以下のようなものがあります。 - `(1+1+1)*(1+1+1)` - `1+1+1+1+1+1+1+1+1` - `(1+1)*(1+1)*(1+1)+1` 値が $ 9 $ となるような数式のうち、長さが最小となるものは `(1+1+1)*(1+1+1)` です。 ### Constraints - $ 1\leq N\leq 2000 $ - 入力は全て整数