Problem: Problem

Satake doesn't like being bent.
For example, I don't like pencils, chopsticks, and bent-shaped houses, and I don't like taking actions such as turning right or left.

By the way, Satake who lives on the XY plane is $ N $ shops $ (X_ {1}, Y_ {1}), (X_ {2}, Y_ {2}), \ ldots, (X_ {N} , Y_ {N}) I was asked to shop for $. Depart from the house at coordinates $ (0, 0) $ in the direction of $ (1, 0) $, shop at all stores, and then return home. You can go around the shops in any order. As a user, Satake can perform any of the following actions as many times as you like.

1. Go as much as you like in the direction you are facing
2. When the coordinates are the same as the shop or house, rotate clockwise or counterclockwise by the desired angle on the spot.
3. When the coordinates are the same as the store, shop while maintaining the coordinates and the direction in which they are facing.



As I said earlier, Satake doesn't like to bend. To prepare your mind, find the minimum sum of the angles that Satake will rotate in Action 2. As an example, if you rotate $ 90 ^ {\ circ} $ clockwise and then $ 90 ^ {\ circ} $ counterclockwise, the sum of the angles will be $ 180 ^ {\ circ} $.

Constraints

The input meets the following conditions:

* $ 2 \ le N \ le 8 $
* $ -1000 \ le X_ {i}, Y_ {i} \ le 1000 \ quad (1 \ le i \ le N) $
* $ (X_ {i}, Y_ {i}) \ ne (0, 0) \ quad (1 \ le i \ le N) $
* $ (X_ {i}, Y_ {i}) \ ne (X_ {j}, Y_ {j}) \ quad (i \ ne j) $
* All inputs are integers

Input

The input is given in the following format:


$ N $
$ X_ {1} $ $ Y_ {1} $
$ \ vdots $
$ X_ {N} $ $ Y_ {N} $


The input consists of $ N + 1 $ lines.
The $ 1 $ line is given $ N $, which represents the number of stores to shop.
The $ N $ line starting from the $ 2 $ line is given the coordinates $ X_ {i}, Y_ {i} $ of the store where you shop, separated by blanks.

Output

Please output the minimum value of the sum of the angles that Satake rotates in degrees. However, the correct answer is given only when the absolute error from the assumed solution is $ 10 ^ {-4} $ or less.

Examples

Input

2
0 1
0 -1


Output

450.00000000


Input

3
1 0
0 1
-2 -1


Output

386.565051

Solution (in CPP):

Solution:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <cstdint>
using namespace std;
typedef long long ll;
#define MP make_pair
#define PB push_back
#define inf 1000000007
#define mod 1000000007
#define rep(i,n) for(int i = 0; i < (int)(n); ++i)
#define EPS 1e-10

typedef complex<double> C;

const double PI = 4*atan(1.0);

bool eq(double a,double b)
{
  return (-EPS<a-b&&a-b<EPS);
}

namespace std
{
    bool operator < (const C a, const C b) {
        return a.real() != b.real() ? a.real() < b.real() : a.imag() < b.imag();
    }
    bool operator > (const C a, const C b) {
        return a.real() != b.real() ? a.real() > b.real() : a.imag() > b.imag();
    }
    bool operator==(const C a, const C b){
        return (eq(a.real(),b.real()) && eq(a.imag(),b.imag()));
    }
    bool operator!=(const C a, const C b){
        return !(a == b);
    }
    C operator* (const C a, const C b){
        return C(a.real()*b.real()-a.imag()*b.imag(),a.real()*b.imag()+a.imag()*b.real());
    }
}

//条件付きsqrt
double Sqrt(double x)
{
    if(x<0) return 0;
    else    return sqrt(x);
}

//正規化
C normalize(C c)
{
    return c / abs(c);
}

//角度(rad)
double getarg(C a,C b){
    return arg(b*conj(a));
}

//外積
double cross(const C a, const C b)
{
    return imag(conj(a)*b);
}
//内積
double dot(const C a, const C b)
{
    return real(conj(a)*b);
}

//bを中心としてaをth(rad)回転
C rot(C a,C b,double th)
{
    return b + (a-b) * C(cos(th),sin(th));
}

int ccw(C a, C b, C c)
{
    b -= a; c -= a;
    if(cross(b, c) > 0)   return +1;       // counter clockwise
    if(cross(b, c) < 0)   return -1;       // clockwise
    if(dot(b, c) < 0)     return +2;       // c--a--b on line
    if(norm(b) < norm(c)) return -2;       // a--b--c on line
    return 0;   // a--c--b on line
}

double dp[10][10][1<<9];
vector<double> x,y;
double calc(int i,int j,int k){
    C c1(x[i]-x[j],y[i]-y[j]);
    C c2(x[k]-x[i],y[k]-y[i]);
    return abs(getarg(c1,c2)/M_PI*180.0);
}

int main(){
    int n;
    cin >> n;
    x.resize(n);
    y.resize(n);
    rep(i,n){
        cin >> x[i] >> y[i];
    }
    
    // rep(i,n+1){
    //     rep(j,n+1){
    //         rep(k,1<<n){
    //             dp[i][j][k] = inf;
    //         }
    //     }
    // }
    // rep(i,n+1){
    //     if(i==0)continue;
    //     C c1(1,0);
    //     C c2(x[i],y[i]);
        
    //     dp[i][0][1<<(i-1)] = abs(getarg(c1,c2)/M_PI*180.0);
    //     //cerr << i << " " << 0 << " " << dp[i][0][1<<(i-1)] << endl;
    // }
    
    // rep(i,n+1){
    //     if(i==0)continue;
    //     rep(j,n+1){
    //         rep(k,1<<n){
    //             if(abs(dp[i][j][k]-inf)<=EPS){
    //                 continue;
    //             }
    //             //cerr << i << " " << j << " " << k << endl;
    //             rep(l,n){
    //                 if((k>>l)&1){

    //                 }else{
    //                     int id = l+1;
    //                     //cerr << id << endl;
    //                     dp[id][i][k^(1<<l)] = min(dp[id][i][k^(1<<l)],dp[i][j][k]+calc(i,j,id));
    //                     //cerr << dp[id][i][k^(1<<l)] << endl;
    //                 }
    //             }
    //         }
    //     }
    // }
    // double mi = inf;
    // rep(i,n+1){
    //     rep(j,n+1){
    //         if(i==0||j==0)continue;
    //         if(i==j)continue;
    //         //cerr << i << " " << j << " " << dp[i][j][(1<<n)-1]  << " " <<  calc(i,j,0) << endl;
    //         mi = min(mi,dp[i][j][(1<<n)-1] + calc(i,j,0));
    //     }
    // }
    vector<int>v(n);
    rep(i,n){
        v[i] = i;
    }
    double mi = inf;
    do{
        C c1(1,0);
        C p(0,0);
        double tmp  = 0;
        rep(i,n){
            C c2(x[v[i]]-p.real(),y[v[i]]-p.imag());
            tmp +=  abs(getarg(c1,c2)/M_PI*180.0);
            p = C(x[v[i]],y[v[i]]);
            c1 = c2;
            //cerr << p << " " << c2 << endl;
        }
        C c3(-x[v[n-1]],-y[v[n-1]]);
        tmp +=  abs(getarg(c1,c3)/M_PI*180.0);
            
        mi = min(mi,tmp );

    }while(next_permutation(v.begin(),v.end()));
    cout.precision(20);
    cout << mi << endl;
    return 0;
}