namespace ProjectEuler {
    class Program {
        static void Main(string[] args) {
            new Problem○○(); // ○○は問題番号
        }
    }
}

using System;

namespace ProjectEuler {
    public class Problem {
        public Problem() {
            Console.WriteLine(this.ToString());
        }
    }
}

using System;
using System.Collections.Generic;
using System.Text;

namespace ProjectEuler {
    public class BigInt : ICloneable{
        /// <summary>
        /// 値を表す32ビット値のリスト
        /// 先頭が最も上位を表す
        /// </summary>
        List<UInt32> m_value = new List<UInt32>();

        /// <summary>
        /// 値を表すリストの長さを取得する
        /// </summary>
        public int Length {
            get {
                return m_value.Count;
            }
        }

        public UInt32 this[int n] {
            get {
                if (n >= Length) {
                    return 0;//error?
                } else if (n >= 0) {
                    return m_value[n];//ok
                } else {
                    return 0;//error?
                }
            }
            set {
                m_value[n] = value;
            }
        }

        /// <summary>
        /// 0で初期化
        /// </summary>
        public BigInt() {
            Initialize();
        }

        /// <summary>
        /// 32ビット整数で初期化
        /// </summary>
        /// <param name="n"></param>
        public BigInt(UInt32 n) {
            m_value.Add(n);
        }

        public void Initialize() {
            m_value = new List<uint>();
            m_value.Add(0);
        }

        int RIndex(int n) {
            //if(n < Length)
            return Length - 1 - n;

        }

        /// <summary>
        /// 10のn乗の値を取得する
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public static BigInt PowOf10(int digits) {

            BigInt bi = new BigInt(1);
            bi.Multiple((int)Math.Pow(10, (digits) % 9));
            for (int i = (digits) / 9; i > 0; i--) {
                bi.Multiple(1000000000);
            }
            return bi;
        }

        /// <summary>
        /// 十進文字列に変換する
        /// </summary>
        /// <returns></returns>
        public string ToDec() {
            StringBuilder ret = new StringBuilder();
            UInt32 mod = 0;
            BigInt bi = BigInt.FromArray(m_value);
            while (true) {
                bi = bi.DivMod10(out mod);
                ret.Insert(0, mod);
                if (bi < 10) {
                    ret.Insert(0, bi.m_value[0]);
                    break;
                }
            }
            return ret.ToString();
        }

        /// <summary>
        /// 32ビット整数の乗算を行う
        /// </summary>
        /// <param name="n"></param>
        public void Multiple(int n) {
            UInt64 v = 0;
            UInt32 u = 0;
            for (int i = 0; i < Length; i++) {
                v = (UInt64)this[RIndex(i)];
                v *= (UInt64)n;
                v += u;
                this[RIndex(i)] = (UInt32)v;
                u = (UInt32)(v>>32);
            }
            if (u != 0) {
                m_value.Insert(0, (UInt32)u);
            }
        }


        public void Divide(int div) {
            UInt64 a = 0, b = 0;
            for (int i = 0; i < Length; i++) {
                b += this[i];
                a = b / (UInt64)div;
                b = b % (UInt64)div;
                this[i] = (UInt32)a;
                b <<= 32;
            }
            if (this[0] == 0) {
                m_value.RemoveAt(0);
            }
        }

        /// <summary>
        /// 10で割った時の商と余りを取得する
        /// </summary>
        /// <param name="mod"></param>
        /// <returns></returns>
        public BigInt DivMod10(out UInt32 mod) {
            UInt64 x = 0, m = 0;
            BigInt bi = new BigInt();

            for (int i = 0; i<m_value.Count; i++, x = 0) {
                x = (UInt64)(m_value[i] + (m << 32));
                m = x % 10;
                bi.AppendList((UInt32)(x / 10));
            }
            mod = (UInt32)m;

            return bi;
        }

        /// <summary>
        /// 値を表すリストの末尾に32ビットを追加する
        /// </summary>
        /// <param name="value"></param>
        /// <returns></returns>
        public BigInt AppendList(UInt32 value) {
            if (m_value[0] == 0) {
                m_value[0] = value;
            } else {
                m_value.Add(value);
            }
            return this;
        }

        /// <summary>
        /// 配列から読み込む
        /// </summary>
        /// <param name="array"></param>
        /// <returns></returns>
        public static BigInt FromArray(List<UInt32> array) {
            BigInt bi = new BigInt();
            foreach (UInt32 i in array) {
                bi.AppendList(i);
            }
            return bi;
        }

        public static BigInt operator +(BigInt a, BigInt b){
            BigInt ret = new BigInt();
            ret.m_value.Clear();
            int length = Math.Max(a.Length, b.Length);
            UInt64 x = 0;

            for (int i = 0; i < length; i++) {
                x += ((UInt64)a[a.RIndex(i)] + (UInt64)b[b.RIndex(i)]);
                ret.m_value.Insert(0,(UInt32)x);
                x >>= 32;
            }
            if (x != 0) {
                ret.m_value.Insert(0,(UInt32)x);
            }
            return ret;
        }

        public static BigInt operator /(BigInt a, int b) {
            BigInt ret = (BigInt)a.Clone();
            ret.Divide(b);
            return ret;
        }

        /// <summary>
        /// 比較
        /// </summary>
        /// <param name="bi"></param>
        /// <param name="a"></param>
        /// <returns></returns>
        public static bool operator <(BigInt bi, int a) {
            if (bi.m_value.Count > 1) {
                return false;
            }
            return bi.m_value[0] < a;
        }

        /// <summary>
        /// 比較
        /// </summary>
        /// <param name="bi"></param>
        /// <param name="a"></param>
        /// <returns></returns>
        public static bool operator >(BigInt bi, int a) {
            if(bi.m_value.Count > 1){
                return true;
            }
            return bi.m_value[0] > a;
        }

        /// <summary>
        /// 比較
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static bool operator <(BigInt a, BigInt b) {
            if (a.Length == b.Length) {
                for (int i = 0; i < a.Length; i++) {
                    if (a[i] > b[i]) {
                        return false;
                    } else if (a[i] < b[i]) {
                        return true;
                    }
                }
            }
            return a.Length < b.Length;
        }

        /// <summary>
        /// 比較
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static bool operator >(BigInt a, BigInt b) {
            if (a.Length == b.Length) {
                for (int i = 0; i < a.Length; i++) {
                    if (a[i] < b[i]) {
                        return false;
                    }else if(a[i] > b[i]){
                        return true;
                    }
                }
            }
            return a.Length > b.Length;
        }

        /// <summary>
        /// 比較
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static bool operator <=(BigInt a, BigInt b) {
            return (a < b) || (a == b);
        }

        /// <summary>
        /// 比較
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static bool operator >=(BigInt a, BigInt b) {
            return (a > b) || (a == b);
        }

        /// <summary>
        /// 比較
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static bool operator ==(BigInt a, UInt32 b) {
            return (a.Length == 1 && a[0] == b);
        }

        /// <summary>
        /// 比較
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static bool operator !=(BigInt a, UInt32 b) {
            return !(a == b);
        }

        /// <summary>
        /// 比較
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static bool operator ==(BigInt a, BigInt b) {
            if (a.Length != b.Length)
                return false;
            for (int i = 0; i < a.Length; i++) {
                if (a[a.RIndex(i)] != b[b.RIndex(i)]) {
                    return false;
                }
            }
            return true;
        }

        /// <summary>
        /// 比較
        /// </summary>
        /// <param name="a"></param>
        /// <param name="b"></param>
        /// <returns></returns>
        public static bool operator !=(BigInt a, BigInt b) {
            return !(a == b);
        }

        /// <summary>
        /// 左シフト
        /// </summary>
        /// <param name="b"></param>
        /// <param name="shift"></param>
        /// <returns></returns>
        public static BigInt operator <<(BigInt b, int shift) {
            BigInt bi = (BigInt)b.Clone();
            int m = shift / 32,
                n = shift % 32;
            if (n != 0) {
                UInt64 a = 0;
                UInt32 c = 0;
                for (int i = bi.m_value.Count - 1; i >= 0; --i) {
                    a = bi.m_value[i];
                    a <<= n;
                    a |= c;
                    bi.m_value[i] = (UInt32)a;
                    c = (UInt32)(a >> 32);
                }
                if (c != 0) {
                    bi.m_value.Insert(0, c);
                }
            }
            for (int i = 0; i<m;i++ ) {
                bi.AppendList(0);
            }
            return bi;
        }

        public static implicit operator BigInt(int n) {
            return new BigInt((uint)n);
        }

        public override int GetHashCode() {
            int hash = 0;
            foreach(ulong v in m_value){
                hash ^= (int)v;
            }
            return hash;
        }

        #region ICloneable
        public object Clone() {
            BigInt bi = new BigInt();
            foreach (var i in m_value) {
                bi.AppendList(i);
            }
            return bi;
        }
        #endregion
    }
}

using System;
using System.Collections.Generic;
using System.Linq;

namespace ProjectEuler {
    public class Primes {
       
        private List<long> m_table = null;

        /// <summary>
        /// テーブルに存在する素数の数を取得する
        /// </summary>
        public int Count{
            get{
                if (m_table == null) {
                    return 0;
                }
                return m_table.Count;
            }
        }

        /// <summary>
        /// テーブル上の最大素数の値を取得する
        /// </summary>
        public long MaxValue {
            get {
                if (m_table == null) {
                    return 0;
                }
                return m_table.Last();
            }
        }

        /// <summary>
        /// n番目の素数の値を取得する
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public long this[int index] {
            get {
                if (index > Count) {
                    Make(index);
                }
                return m_table[index];
            }
        }

        public Primes() {
            m_table = new List<long>();
        }

        /// <summary>
        /// 少なくともn番目までの素数テーブルを作成する
        /// </summary>
        /// <param name="n"></param>
        public Primes(int n){
            m_table = new List<long>(n);
            Make(n);
        }

        /// <summary>
        /// 少なくともn番目までの素数テーブルを作成する
        /// </summary>
        /// <param name="n"></param>
        public void Make(int n) {
            bool isPrime;
            long number = 3;

            Initialize();
            if (m_table.Count > n) {
                return;
            }

            for (number = MaxValue+2;; number += 2) {
                isPrime = true;
                foreach (var m in m_table) {
                    if (number % m == 0) {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime) {
                    m_table.Add(number);
                    if (m_table.Count >= n) {
                        break;
                    }
                }
            }
        }

        /// <summary>
        /// n以下の素数テーブルを作成する
        /// </summary>
        /// <param name="n"></param>
        public void MakeUnder(long n) {
            bool isPrime;
            long number = 3;

            Initialize();
            if (MaxValue > n) {
                return;
            }

            for (number = MaxValue + 2; ; number += 2) {
                isPrime = true;
                foreach (var m in m_table) {
                    if (number % m == 0) {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime) {
                    m_table.Add(number);
                    if (number >= n) {
                        break;
                    }
                }
            }
        }

        private void Initialize() {
            if (m_table.Count == 0) {
                m_table.Add(2);
                m_table.Add(3);
            }
        }

        public bool IsPrime(long n) {
            if (n <= MaxValue) {
                return m_table.Contains(n);
            }
            MakeUnder(n);
            return IsPrime(n);
        }

        /// <summary>
        /// 素因数分解を行う
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public Dictionary<long, int> PrimeFactors(long n) {
            Dictionary<long, int> primes = new Dictionary<long, int>();
            for (int i = 0; n > 1; ) {
                if(i+1 > Count){
                    Make(i+10);
                }
                if (n % m_table[i] == 0) {
                    n /= m_table[i];
                    if (primes.ContainsKey(m_table[i])) {
                        ++primes[m_table[i]];
                    } else {
                        primes.Add(m_table[i], 1);
                    }
                    continue;
                }
                ++i;
            }
            if (n > 1) {
                primes[n] = 1;
            }
            return primes;
        }
    }
}

using System;
using System.Collections.Generic;
using System.Linq;

namespace ProjectEuler {
    class Numerics {

        public static List<long> Divisors(long n) {
            List<long> divisors = DivisorsWithoutSelf(n);
            if (divisors.Last() < n) {
                divisors.Add(n);
            }
            return divisors;
        }

        public static List<long> DivisorsWithoutSelf(long n) {
            List<long> divisors = new List<long>();
            long rt = (long)Math.Sqrt((double)n);
            bool isSquare = rt * rt == n;

            if (n > 0) {
                divisors.Add(1);
            }
            for (long i = 2; i <= rt; i++) {
                if (n % i == 0) {
                    divisors.Add(i);
                }
            }
            for (int i = divisors.Count - (isSquare ? 2 : 1); i > 0; i--) {
                divisors.Add(n / divisors[i]);
            }
            return divisors;
        }
    }
}