Lê Quang Lâm - TK33

#include <iostream>
#include <queue>
#include <vector>

// llprime.*

using namespace std;

bool prime(int u)
{
    if (u <= 1) return false;
    for (int i = 2; i * i <= u; i++)
        if (u % i == 0)
        return false;
    return true;
}

void xuli()
{
    int n, t;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < n; i++)
    {
        cin >> t;
        pq.push(t);
    }
    bool p = false;
    while (!pq.empty())
    {
        t = pq.top();
        if (prime(t))
        {
            p = true;
            cout << t << " ";
        }
        pq.pop();
    }
    if (!p)
        cout << -1;
}

int main()
{
    freopen("llprime.inp","r",stdin);
    freopen("llprime.out","w",stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <vector>

// cpprime.*

using namespace std;

bool prime(long long u)
{
    if (u <= 1) return false;
    for (long long i = 2; i * i <= u; i++)
        if (u % i == 0)
        return false;
    return true;
}

void xuli()
{
    vector<int> a;
    int t;
    size_t n;
    cin >> n;
    for (size_t i = 0; i < n; i++)
    {
        cin >> t;
        a.push_back(t);
    }
    int cnt = 0;
    for (size_t i = 0; i < n - 1; i++)
        for (size_t j = i + 1; j < n; j++)
        {
            if (prime(a[i] + a[j]))
                cnt++;
        }
    cout << cnt;
}

int main()
{
    freopen("cpprime.inp","r",stdin);
    freopen("cpprime.out","w",stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <vector>

// cpprime.* (method 2)

using namespace std;

void xuli()
{
    vector<int> a;
    int t;
    size_t n;
    cin >> n;
    int amax = INT_MIN;
    for (size_t i = 0; i < n; i++)
    {
        cin >> t;
        a.push_back(t);
        amax = max(amax, t);
    }
    amax *= 2;
    vector<bool> f;
    f.resize(amax + 1);
    f[0] = false;
    f[1] = false;
    for (int i = 2; i <= amax; i++)
        f[i] = true;
    for (int i = 2; i * i <= amax; i++)
        if (f[i])
            for (int j = i * i; j <= amax; j += i)
                f[j] = false;
    int cnt = 0;
    for (size_t i = 0; i < n - 1; i++)
        for (size_t j = i + 1; j < n; j++)
        {
            if (f[a[i] + a[j]])
                cnt++;
        }
    cout << cnt;
}

int main()
{
    freopen("cpprime.inp","r",stdin);
    freopen("cpprime.out","w",stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <queue>
#include <vector>

// arrayadd1.*

using namespace std;

long long res;
vector<vector<int>> c;
vector<int> a;
vector<int> b;

void print_result(size_t n)
{
    long long s = 1;
    for (size_t i = 0; i < n; i++)
        if (b[i] == 1)
            s *= a[i];
    if (res <= s)
    {
        if (res < s)
            c.clear();
        vector<int> tmp (b.begin(), b.end());
        c.push_back(tmp);
        res = s;
    }
}

void bincnt(size_t n, size_t i)
{
    for (int j = 0; j <= 1; j++)
    {
        b[i] = j;
        if (i == n - 1)
            print_result(n);
        else
            bincnt(n, i + 1);
    }
}

void xuli()
{
    size_t n;
    cin >> n;
    int t;
    for (size_t i = 0; i < n; i++)
    {
        cin >> t;
        a.push_back(t);
    }
    b.resize(n);
    res = LONG_MIN;
    bincnt(n, 0);
    for (size_t k = 0; k < c.size(); k++)
    {
        vector<int> tmp = c[k];
        for (size_t i = 0; i < n; i++)
            cout << tmp[i] << " ";
        cout << endl;
    }
    cout << res;
}

int main()
{
    freopen("arrayadd1.inp","r",stdin);
    freopen("arrayadd1.out","w",stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

// arrayadd1.* (method 2)

using namespace std;

typedef pair<int, size_t> my_pair;
class mycomp
{
    public:
    bool operator() (my_pair& lhs, my_pair& rhs)
    {
        return lhs.first > rhs.first;
    }
};

bool cmp(my_pair lhs, my_pair rhs)
{
    return lhs.second < rhs.second;
}

void xuli()
{
    size_t n;
    cin >> n;
    vector<my_pair> d;
    vector<my_pair> e;
    priority_queue<my_pair, vector<my_pair>, mycomp> pq;
    long long s1 = 1, s2 = 1;
    for (size_t i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        if (t < 0)
        {
            pq.push(make_pair(t, i));
        }
        else
        {
            d.push_back(make_pair(t, i));
            s1 *= t;
        }
    }
    bool p = pq.size() % 2 == 1;
    while (pq.size() > (p ? 1 : 0))
    {
        my_pair t = pq.top();
        s2 *= t.first;
        e.push_back(t);
        pq.pop();
    }
    cout << s1 * s2 << endl;
    vector<my_pair> q (d.begin(), d.end());
    for (size_t i = 0; i < e.size(); i++)
        q.push_back(e[i]);
    sort(q.begin(), q.end(), cmp);
    for (size_t i = 0; i < q.size(); i++)
    {
        my_pair t = q[i];
        cout << t.first << " ";
    }
}

int main()
{
    freopen("arrayadd1.inp","r",stdin);
    freopen("arrayadd1.out","w",stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <queue>
#include <vector>

// arrayadd2.*

using namespace std;

vector<vector<int>> c;
vector<int> a;
vector<int> b;

bool prime(long long u)
{
    if (u <= 1) return false;
    for (long long i = 2; i * i <= u; i++)
        if (u % i == 0)
        return false;
    return true;
}

void print_result(size_t n)
{
    long long s = 0;
    for (size_t i = 0; i < n; i++)
        if (b[i] == 1)
            s += a[i];
    if (prime(s))
    {
        vector<int> tmp (b.begin(), b.end());
        c.push_back(tmp);
    }
}

void bincnt(size_t n, size_t i)
{
    for (int j = 0; j <= 1; j++)
    {
        b[i] = j;
        if (i == n - 1)
            print_result(n);
        else
            bincnt(n, i + 1);
    }
}

void xuli()
{
    size_t n;
    cin >> n;
    int t;
    for (size_t i = 0; i < n; i++)
    {
        cin >> t;
        a.push_back(t);
    }
    b.resize(n);
    bincnt(n, 0);
    for (size_t k = 0; k < c.size(); k++)
    {
        vector<int> tmp = c[k];
        for (size_t i = 0; i < n; i++)
            cout << tmp[i] << " ";
        cout << endl;
    }
}

int main()
{
    freopen("arrayadd2.inp","r",stdin);
    freopen("arrayadd2.out","w",stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <vector>

// arrayadd3.*

using namespace std;

bool prime(long long u)
{
    if (u <= 1) return false;
    for (long long i = 2; i * i <= u; i++)
        if (u % i == 0)
        return false;
    return true;
}

void xuli()
{
    size_t n;
    cin >> n;
    vector<int> a;
    vector<vector<int>> c;
    for (size_t i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        a.push_back(t);
    }
    long long res = 0;
    for (size_t i = 0; i < n - 2; i++)
        for (size_t j = i + 1; j < n - 1; j++)
            for (size_t k = j + 1; k < n; k++)
            {
                long long t = a[i] + a[j] + a[k];
                if (prime(t) && res <= t)
                {
                    if (res < t)
                        c.clear();
                    vector<int> tmp;
                    tmp.push_back(a[i]);
                    tmp.push_back(a[j]);
                    tmp.push_back(a[k]);
                    c.push_back(tmp);
                    res = t;
                }
            }
    for (size_t k = 0; k < c.size(); k++)
    {
        vector<int> tmp = c[k];
        for (size_t i = 0; i < 3; i++)
            cout << tmp[i] << " ";
        cout << endl;
    }
}

int main()
{
    freopen("arrayadd3.inp","r",stdin);
    freopen("arrayadd3.out","w",stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <string>
#include <vector>

// arrayadd4.*

using namespace std;

long long res;
vector<vector<int>> c;
vector<int> a;
vector<int> b;
int k;

bool palin(long long u)
{
    string s = to_string(u);
    size_t n = s.size();
    string s1 = "";
    for (size_t i = 0; i < n; i++)
    {
        s1 = s[i] + s1;
    }
    return s == s1;
}

void print_result(size_t n)
{
    long long s = 1;
    int cnt = 0;
    for (size_t i = 0; i < n; i++)
        if (b[i] == 1)
        {
            s += a[i];
            cnt++;
        }
    if (cnt != k || !palin(s))
        return;
    if (res <= s)
    {
        if (res < s)
            c.clear();
        vector<int> tmp (b.begin(), b.end());
        c.push_back(tmp);
        res = s;
    }
}

void bincnt(size_t n, size_t i)
{
    for (int j = 0; j <= 1; j++)
    {
        b[i] = j;
        if (i == n - 1)
            print_result(n);
        else
            bincnt(n, i + 1);
    }
}

void xuli()
{
    size_t n;
    cin >> n;
    cin >> k;
    int t;
    for (size_t i = 0; i < n; i++)
    {
        cin >> t;
        a.push_back(t);
    }
    b.resize(n);
    res = LONG_MIN;
    bincnt(n, 0);
    for (size_t j = 0; j < c.size(); j++)
    {
        vector<int> tmp = c[j];
        for (size_t i = 0; i < n; i++)
            if (tmp[i] == 1)
            cout << a[i] << " ";
        cout << endl;
    }
    cout << res;
}

int main()
{
    freopen("arrayadd4.inp","r",stdin);
    freopen("arrayadd4.out","w",stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <vector>

// arrayadd5.*

using namespace std;

long long fib[104];
vector<vector<int>> c;
vector<int> a;
vector<int> b;

void initfib()
{
    fib[1] = 1;
    fib[2] = 1;
    for (int i = 3; i <= 103; i++)
    {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
}

bool isfib(long long u)
{
    for (int i = 1; i <= 103; i++)
        if (u == fib[i])
            return true;
    return false;
}

void print_result(size_t n)
{
    long long s = 0;
    for (size_t i = 0; i < n; i++)
        if (b[i] == 1)
            s += a[i];
    if (isfib(s))
    {
        vector<int> tmp (b.begin(), b.end());
        c.push_back(tmp);
    }
}

void bincnt(size_t n, size_t i)
{
    for (int j = 0; j <= 1; j++)
    {
        b[i] = j;
        if (i == n - 1)
            print_result(n);
        else
            bincnt(n, i + 1);
    }
}

void xuli()
{
    initfib();
    size_t n;
    cin >> n;
    int t;
    for (size_t i = 0; i < n; i++)
    {
        cin >> t;
        a.push_back(t);
    }
    b.resize(n);
    bincnt(n, 0);
    for (size_t k = 0; k < c.size(); k++)
    {
        vector<int> tmp = c[k];
        for (size_t i = 0; i < n; i++)
            if (tmp[i] == 1)
            cout << a[i] << " ";
        cout << endl;
    }
}

int main()
{
    freopen("arrayadd5.inp","r",stdin);
    freopen("arrayadd5.out","w",stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <vector>

// qhd1.*

using namespace std;

void xuli()
{
    size_t n, p;
    cin >> n >> p;
    vector<int> a;
    vector<pair<size_t, size_t>> b;
    vector<long long> c;
    for (size_t i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        a.push_back(t);
    }
    for (size_t i = 0; i < p; i++)
    {
        size_t t1, t2;
        cin >> t1 >> t2;
        b.push_back(make_pair(t1, t2));
    }
    c.push_back(0);
    c.push_back(a[0]);
    for (size_t i = 1; i < n; i++)
    {
        long long t = c[i] + a[i];
        c.push_back(t);
    }
    for (size_t i = 0; i < p; i++)
    {
        pair<size_t, size_t> t = b[i];
        long long res = c[t.second] - c[t.first - 1];
        cout << res << endl;
    }
}

int main()
{
    freopen("qhd1.inp","r",stdin);
    freopen("qhd1.out","w",stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <vector>

// qhd3.*

using namespace std;

bool prime(long long u)
{
    if (u <= 1) return false;
    for (long long i = 2; i * i <= u; i++)
        if (u % i == 0)
        return false;
    return true;
}

void xuli()
{
    size_t n, p;
    cin >> n >> p;
    vector<int> a;
    vector<pair<size_t, size_t>> b;
    vector<long long> c;
    for (size_t i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        a.push_back(t);
    }
    for (size_t i = 0; i < p; i++)
    {
        size_t t1, t2;
        cin >> t1 >> t2;
        b.push_back(make_pair(t1, t2));
    }
    c.push_back(0);
    c.push_back(a[0]);
    for (size_t i = 1; i < n; i++)
    {
        long long t = c[i] + a[i];
        c.push_back(t);
    }
    long long res = -1;
    for (size_t i = 0; i < p; i++)
    {
        pair<size_t, size_t> t = b[i];
        long long r = c[t.second] - c[t.first - 1];
        if (prime(r))
            res = max(res, r);
    }
    cout << res;
}

int main()
{
    freopen("qhd3.inp","r",stdin);
    freopen("qhd3.out","w",stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <vector>

// qhd4.*

using namespace std;

bool prime(long long u)
{
    if (u <= 1) return false;
    for (long long i = 2; i * i <= u; i++)
        if (u % i == 0)
        return false;
    return true;
}

int divcnt(long long n)
{
    int cnt = 0;
    for (long long i = 1; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            cnt++;
            if (i != n / i)
            {
                cnt++;
            }
        }
    }
    return cnt;
}

void xuli()
{
    size_t n, p;
    int k;
    cin >> n >> p >> k;
    vector<int> a;
    vector<pair<size_t, size_t>> b;
    vector<long long> c;
    for (size_t i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        a.push_back(t);
    }
    for (size_t i = 0; i < p; i++)
    {
        size_t t1, t2;
        cin >> t1 >> t2;
        b.push_back(make_pair(t1, t2));
    }
    c.push_back(0);
    c.push_back(a[0]);
    for (size_t i = 1; i < n; i++)
    {
        long long t = c[i] + a[i];
        c.push_back(t);
    }
//    long long res = -1;
    for (size_t i = 0; i < p; i++)
    {
        pair<size_t, size_t> t = b[i];
        long long r = c[t.second] - c[t.first - 1];
        if (k == divcnt(r))
            cout << r << endl;
//        res = max(res, r);
    }
//    cout << res;
}

int main()
{
    freopen("qhd4.inp","r",stdin);
    freopen("qhd4.out","w",stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <vector>
#include <string>

// qhd5.*

using namespace std;

bool prime(long long u)
{
    if (u <= 1) return false;
    for (long long i = 2; i * i <= u; i++)
        if (u % i == 0)
        return false;
    return true;
}

int divcnt(long long n)
{
    int cnt = 0;
    for (long long i = 1; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            cnt++;
            if (i != n / i)
            {
                cnt++;
            }
        }
    }
    return cnt;
}

bool palin(long long u)
{
    string s = to_string(u);
    size_t n = s.size();
    string s1 = "";
    for (size_t i = 0; i < n; i++)
    {
        s1 = s[i] + s1;
    }
    return s == s1;
}

void xuli()
{
    size_t n, p;
    cin >> n >> p;
    vector<int> a;
    vector<pair<size_t, size_t>> b;
    vector<long long> c;
    for (size_t i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        a.push_back(t);
    }
    for (size_t i = 0; i < p; i++)
    {
        size_t t1, t2;
        cin >> t1 >> t2;
        b.push_back(make_pair(t1, t2));
    }
    c.push_back(0);
    c.push_back(a[0]);
    for (size_t i = 1; i < n; i++)
    {
        long long t = c[i] + a[i];
        c.push_back(t);
    }
//    long long res = -1;
    for (size_t i = 0; i < p; i++)
    {
        pair<size_t, size_t> t = b[i];
        long long r = c[t.second] - c[t.first - 1];
        if (palin(r))
            cout << r << endl;
//        res = max(res, r);
    }
//    cout << res;
}

int main()
{
    freopen("qhd5.inp","r",stdin);
    freopen("qhd5.out","w",stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

// qhd6.*

using namespace std;

bool perfsq(long long u)
{
    double t = sqrt(u);
    return t == (long long) t;
}

void xuli()
{
    size_t n, p;
    cin >> n >> p;
    vector<int> a;
    vector<pair<size_t, size_t>> b;
    vector<long long> c;
    for (size_t i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        a.push_back(t);
    }
    for (size_t i = 0; i < p; i++)
    {
        size_t t1, t2;
        cin >> t1 >> t2;
        b.push_back(make_pair(t1, t2));
    }
    c.push_back(0);
    c.push_back(a[0]);
    for (size_t i = 1; i < n; i++)
    {
        long long t = c[i] + a[i];
        c.push_back(t);
    }
//    long long res = -1;
    for (size_t i = 0; i < p; i++)
    {
        pair<size_t, size_t> t = b[i];
        long long r = c[t.second] - c[t.first - 1];
        if (perfsq(r))
            cout << r << endl;
//        res = max(res, r);
    }
//    cout << res;
}

int main()
{
    freopen("qhd6.inp","r",stdin);
    freopen("qhd6.out","w",stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

// qhd6.*

using namespace std;

bool perfsq(long long u)
{
    double t = sqrt(u);
    return t == (long long) t;
}

void xuli()
{
    size_t n;
    cin >> n;
    vector<int> a;
    vector<long long> c;
    for (size_t i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        a.push_back(t);
    }
    c.push_back(0);
    c.push_back(a[0]);
    for (size_t i = 1; i < n; i++)
    {
        long long t = c[i] + a[i];
        c.push_back(t);
    }
//    long long res = -1;
    for (size_t i = 1; i <= n; i++)
    {
        for (size_t j = i; j <= n; j++)
        {
            long long r = c[j] - c[i - 1];
            if (perfsq(r))
                cout << r << endl;
        }
    }
//    cout << res;
}

int main()
{
    freopen("qhd7.inp","r",stdin);
    freopen("qhd7.out","w",stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

// qhd8.*

using namespace std;

bool prime(long long u)
{
    if (u <= 1) return false;
    for (long long i = 2; i * i <= u; i++)
        if (u % i == 0)
        return false;
    return true;
}

void xuli()
{
    size_t n;
    cin >> n;
    vector<int> a;
    vector<long long> c;
    for (size_t i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        a.push_back(t);
    }
    c.push_back(0);
    c.push_back(a[0]);
    for (size_t i = 1; i < n; i++)
    {
        long long t = c[i] + a[i];
        c.push_back(t);
    }
    long long res = -1;
    for (size_t i = 1; i <= n; i++)
    {
        for (size_t j = i; j <= n; j++)
        {
            long long r = c[j] - c[i - 1];
            if (prime(r))
                res = max(res, r);
        }
    }
    cout << res;
}

int main()
{
    freopen("qhd8.inp","r",stdin);
    freopen("qhd8.out","w",stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

// qhd9.*

using namespace std;

bool prime(long long u)
{
    if (u <= 1) return false;
    for (long long i = 2; i * i <= u; i++)
        if (u % i == 0)
        return false;
    return true;
}

void xuli()
{
    size_t n;
    int k;
    cin >> n >> k;
    vector<int> a;
    vector<long long> c;
    for (size_t i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        a.push_back(t);
    }
    c.push_back(0);
    c.push_back(a[0]);
    for (size_t i = 1; i < n; i++)
    {
        long long t = c[i] + a[i];
        c.push_back(t);
    }
    size_t rlen = 0;
    for (size_t i = 1; i <= n; i++)
    {
        for (size_t j = i; j <= n; j++)
        {
            long long r = c[j] - c[i - 1];
            if (r % k == 0)
                rlen = max(rlen, j - i + 1);
        }
    }
    cout << rlen;
}

int main()
{
    freopen("qhd9.inp","r",stdin);
    freopen("qhd9.out","w",stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <vector>
#include <string>
#include <cmath>

// qhd10.*

using namespace std;

long long fib[104];

void initfib()
{
    fib[1] = 1;
    fib[2] = 1;
    for (int i = 3; i <= 103; i++)
    {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
}

bool isfib(long long x)
{
    int lt = 1, rt = 103;
    while (lt <= rt)
    {
        int m = (lt + rt) / 2;
        if (fib[m] == x)
            return true;
        else if (fib[m] > x)
            rt = m - 1;
        else
            lt = m + 1;
    }
    return false;
}

void xuli()
{
    initfib();
    size_t n;
    cin >> n;
    vector<int> a;
    vector<long long> c;
    for (size_t i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        a.push_back(t);
    }
    c.push_back(0);
    c.push_back(a[0]);
    for (size_t i = 1; i < n; i++)
    {
        long long t = c[i] + a[i];
        c.push_back(t);
    }
    size_t rlen = 0;
    for (size_t i = 1; i <= n; i++)
    {
        for (size_t j = i; j <= n; j++)
        {
            long long r = c[j] - c[i - 1];
            if (isfib(r))
                rlen = max(rlen, j - i + 1);
        }
    }
    cout << rlen;
}

int main()
{
    freopen("qhd10.inp","r",stdin);
    freopen("qhd10.out","w",stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <vector>
#include <cmath>

// qhd12.*

using namespace std;

void xuli()
{
    int n;
    cin >> n;
    int * a = new int[n];
    int res = 0, rl, rr;
    for (int i = 0; i < n; i++)
    {
        int t;
        cin >> t;
        http://a.push_back(t);
        a[i] = t;
    }
    for (int i = 0; i < n; i++)
    {
        //cerr << "a";
        rr = 0;
        for (int j = i + 1; j < n; j++)
            if (a[j] <= a[i])
                rr++;
        //cerr << "b";
        rl = 0;
        for (int j = 0; j <= i - 1; j++)
            if (a[j] >= a[i])
                rl++;
        res = max(res, (int) abs(rr - rl));
    }
    cout << res;
    delete[] a;
}

int main()
{
    freopen("qhd12.inp","r",stdin);
    freopen("qhd12.out","w",stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

// triangle.*

using namespace std;

int *arr, *psum;
long long res;

void sub1(int p)
{
    long long cnt = 0;
    for (int i = 1; i <= p - 2; i++)
        for (int j = i; j <= p - 1; j++)
            for (int k = j; k <= p; k++)
            {
                if ((i + j + 0LL > k) && (k + i + 0LL > j) && (j + k + 0LL > i) && (i + j + k + 0LL == p))
                {
                    cnt++;
                }
            }
    cout << cnt << endl;
}

void sub2(int p)
{
    long long cnt = 0;
    for (int i = 1; i <= p - 2; i++)
        for (int j = i; j <= p - 1; j++)
        {
            int k = p - i - j;
            if ((k >= j) && (i + j + 0LL > k) && (k + i + 0LL > j) && (j + k + 0LL > i))
            {
                //cout << i << " " << j << " " << k << endl;
                cnt++;
            }
        }
    cout << cnt << endl;
}

void thu(int n, int i)
{
    for (int j = arr[i - 1]; j * 2 <= n - psum[i - 1]; j++)
    {
        arr[i] = j;
        psum[i] = psum[i - 1] + j;
        thu(n, i + 1);
    }
    arr[i] = n - psum[i - 1];
    if (i == 3)
    {
        long long a = arr[1], b = arr[2], c = arr[3];
        //cout << a << " " << b << " " << c << endl;
        if((a + b > c) && (c + a > b) && (b + c > a))res++;
    }
}

void sub3(int p)
{
    arr = new int[p + 2];
    psum = new int[p + 2];
    res = 0; psum[0] = 0; arr[0] = 1;
    thu(p, 1);
    cout << res << endl;
    delete[] arr;
    delete[] psum;
}

void xuli()
{
    int p;
    while (cin >> p)
    {
        sub3(p);
    }
}

int main()
{
    freopen("triangle.inp", "r", stdin);
    freopen("triangle.out", "w", stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <string>

// count.*

using namespace std;

void xuli()
{
    int a, b, k;
    while (true)
    {
        cin >> a >> b >> k;
        if (a < 0 || b < 0 || k < 0)
            break;
        int cnt = 0;
        for (int i = a; i <= b; i++)
        {
            string s1 = to_string(i);
            string s2 = to_string(k);
            if (s1.find(s2) != string::npos)
                cnt++;
        }
        cout << cnt << endl;
    }
}

int main()
{
    freopen("count.inp", "r", stdin);
    freopen("count.out", "w", stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

// numjoin.*

using namespace std;

vector<int> a;
size_t n;

bool mycmp(int lhs, int rhs)
{
    string s1 = to_string(lhs);
    string s2 = to_string(rhs);
//    while (s1.size() < s2.size())
//        s1 = s1 + "0";
//    while (s1.size() > s2.size())
//        s2 = s2 + "0";
    return s1 + s2 > s2 + s1;
}

void sub1()
{
    sort(a.begin(), a.end(), mycmp);
    //stable_sort(a.begin(), a.end(), mycmp2);
    for (size_t i = 0; i < n; i++)
        cout << a[i];
    cout << endl;
}

void xuli()
{
    while (true)
    {
        cin >> n;
        if (n == 0)
            break;
        for (size_t i = 0; i < n; i++)
        {
            int t;
            cin >> t;
            a.push_back(t);
        }
        sub1();
        a.clear();
    }
}

int main()
{
    freopen("numjoin.inp", "r", stdin);
    freopen("numjoin.out", "w", stdout);
    xuli();
    return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>

// clear.*

using namespace std;

int dsqsum(int n)
{
    int s = 0;
    while (n > 0)
    {
        int d = n % 10;
        s += d * d;
        n /= 10;
    }
    return s;
}

bool sub1(int n)
{
    vector<int> f;
    int s = n;
    while (true)
    {
        s = dsqsum(s);
        if (s == 1)
            return true;
        if (!f.empty() && find(f.begin(), f.end(), s) != f.end())
            return false;
        //cerr << n << endl;
        f.push_back(s);
    }
}

void submain()
{
    int a, b;
    cin >> a >> b;
    int cnt = 0;
    for (int i = a; i <= b; i++)
        if (sub1(i))
            cnt++;
    cout << cnt;
}

int main()
{
    submain();
    return 0;
}

#include <iostream>
#include <string>

using namespace std;

void sub1(int n)
{
    string s = "1";
    for (int i = 0; i < n; i++)
    {
        string t = s;
        for (size_t j = 0; j < t.size(); j++)
        {
            char c = t[j];
            if (c == '0')
                t[j] = '1';
            else
                t[j] = '0';
        }
        s = t + s;
    }
    int cnt = 0;
    for (size_t i = 0; i < s.size() - 1; i++)
        if ((s[i] == '0') && (s[i + 1] == '0'))
            cnt++;
    cout << cnt << endl;
}

void submain()
{
    int n;
    while (cin >> n)
    {
        sub1(n);
    }
}

int main()
{
    submain();
    return 0;
}

#include <iostream>

// counting.*

using namespace std;

int d[10];

void sub1(int u)
{
    while (u > 0)
    {
        d[u % 10]++;
        u /= 10;
    }
}

void submain()
{
    int a, b;
    while (cin >> a >> b)
    {
        for (int i = 0; i < 10; i++)
            d[i] = 0;
        if (a <= b)
            for (int i = a; i <= b; i++)
                sub1(i);
        else
            for (int i = a; i >= b; i--)
                sub1(i);
        for (int i = 0; i < 10; i++)
            cout << d[i] << " ";
        cout << endl;
    }
}

int main()
{
    freopen("counting.inp", "r", stdin);
    freopen("counting.out", "w", stdout);
    submain();
    return 0;
}