Problem: Dima loves representing an odd number as the sum of multiple primes, and Lisa loves it when there are at most three primes. Help them to represent the given number as the sum of at most than three primes.

More formally, you are given an odd numer n. Find a set of numbers pi (1 ≤ i ≤ k), such that

  1. 1 ≤ k ≤ 3
  2. pi is a prime
  3. <image>



The numbers pi do not necessarily have to be distinct. It is guaranteed that at least one possible solution exists.

Input

The single line contains an odd number n (3 ≤ n < 109).

Output

In the first line print k (1 ≤ k ≤ 3), showing how many numbers are in the representation you found.

In the second line print numbers pi in any order. If there are multiple possible solutions, you can print any of them.

Examples

Input

27


Output

3
5 11 11

Note

A prime is an integer strictly larger than one that is divisible only by one and by itself.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int getint() {
  int _b = 0;
  char _c;
  for (_c = getchar(); _c < '0' || _c > '9'; _c = getchar())
    ;
  for (; _c >= '0' && _c <= '9'; _c = getchar()) {
    _b *= 10;
    _b += _c - '0';
  }
  return _b;
}
bool isp[5000010];
int sta[5000010], t;
vector<int> ans;
const long long prime[] = {
    1000003,   2000003,   3000017,   4000037,   5000011,   6000011,   7000003,
    8000009,   9000011,   10000019,  11000027,  12000017,  13000027,  14000029,
    15000017,  16000057,  17000023,  18000041,  19000013,  20000003,  21000037,
    22000001,  23000009,  24000001,  25000009,  26000003,  27000011,  28000019,
    29000039,  30000001,  31000003,  32000011,  33000001,  34000009,  35000011,
    36000007,  37000039,  38000009,  39000001,  40000003,  41000017,  42000011,
    43000019,  44000003,  45000017,  46000013,  47000011,  48000013,  49000027,
    50000017,  51000041,  52000007,  53000011,  54000031,  55000013,  56000003,
    57000011,  58000003,  59000003,  60000011,  61000001,  62000009,  63000037,
    64000031,  65000011,  66000007,  67000019,  68000003,  69000047,  70000027,
    71000051,  72000007,  73000003,  74000051,  75000007,  76000021,  77000003,
    78000001,  79000007,  80000023,  81000001,  82000031,  83000009,  84000013,
    85000007,  86000009,  87000037,  88000009,  89000027,  90000049,  91000009,
    92000011,  93000007,  94000007,  95000011,  96000011,  97000003,  98000027,
    99000007,  100000007, 101000023, 102000023, 103000039, 104000011, 105000001,
    106000001, 107000009, 108000043, 109000033, 110000017, 111000007, 112000043,
    113000009, 114000001, 115000009, 116000009, 117000049, 118000063, 119000003,
    120000007, 121000003, 122000003, 123000011, 124000001, 125000003, 126000013,
    127000007, 128000003, 129000013, 130000001, 131000021, 132000007, 133000001,
    134000003, 135000007, 136000021, 137000009, 138000001, 139000003, 140000041,
    141000019, 142000003, 143000017, 144000001, 145000033, 146000017, 147000011,
    148000003, 149000017, 150000001, 151000033, 152000047, 153000031, 154000001,
    155000023, 156000011, 157000013, 158000021, 159000019, 160000003, 161000009,
    162000001, 163000003, 164000047, 165000013, 166000007, 167000039, 168000061,
    169000033, 170000009, 171000001, 172000001, 173000017, 174000017, 175000039,
    176000023, 177000007, 178000033, 179000033, 180000017, 181000021, 182000029,
    183000007, 184000021, 185000009, 186000007, 187000019, 188000009, 189000017,
    190000003, 191000041, 192000043, 193000007, 194000011, 195000023, 196000001,
    197000003, 198000001, 199000003, 200000033, 201000049, 202000003, 203000051,
    204000011, 205000001, 206000059, 207000019, 208000007, 209000017, 210000017,
    211000007, 212000003, 213000001, 214000009, 215000033, 216000007, 217000001,
    218000009, 219000011, 220000013, 221000027, 222000019, 223000013, 224000047,
    225000011, 226000007, 227000003, 228000037, 229000019, 230000003, 231000013,
    232000009, 233000023, 234000007, 235000001, 236000027, 237000037, 238000003,
    239000033, 240000011, 241000021, 242000023, 243000007, 244000007, 245000027,
    246000059, 247000001, 248000009, 249000019, 250000013, 251000003, 252000011,
    253000037, 254000023, 255000001, 256000001, 257000011, 258000023, 259000013,
    260000011, 261000007, 262000019, 263000021, 264000001, 265000007, 266000017,
    267000043, 268000001, 269000009, 270000023, 271000001, 272000009, 273000011,
    274000039, 275000051, 276000007, 277000021, 278000053, 279000011, 280000027,
    281000003, 282000073, 283000031, 284000027, 285000013, 286000021, 287000023,
    288000001, 289000001, 290000017, 291000019, 292000013, 293000009, 294000017,
    295000007, 296000051, 297000019, 298000033, 299000011, 300000007, 301000009,
    302000009, 303000001, 304000007, 305000053, 306000011, 307000033, 308000023,
    309000001, 310000037, 311000077, 312000019, 313000001, 314000003, 315000011,
    316000031, 317000011, 318000049, 319000021, 320000077, 321000011, 322000027,
    323000021, 324000029, 325000021, 326000011, 327000029, 328000007, 329000033,
    330000001, 331000001, 332000017, 333000001, 334000013, 335000009, 336000011,
    337000007, 338000009, 339000019, 340000019, 341000021, 342000011, 343000003,
    344000011, 345000001, 346000007, 347000029, 348000001, 349000009, 350000041,
    351000031, 352000007, 353000003, 354000007, 355000007, 356000023, 357000023,
    358000003, 359000009, 360000019, 361000001, 362000003, 363000017, 364000003,
    365000011, 366000023, 367000013, 368000021, 369000029, 370000003, 371000039,
    372000007, 373000007, 374000023, 375000013, 376000003, 377000051, 378000013,
    379000001, 380000009, 381000019, 382000001, 383000003, 384000031, 385000043,
    386000033, 387000013, 388000001, 389000033, 390000041, 391000033, 392000009,
    393000017, 394000027, 395000003, 396000037, 397000049, 398000063, 399000011,
    400000009, 401000011, 402000007, 403000001, 404000033, 405000041, 406000003,
    407000047, 408000001, 409000037, 410000023, 411000011, 412000033, 413000053,
    414000007, 415000021, 416000027, 417000029, 418000003, 419000009, 420000029,
    421000001, 422000009, 423000031, 424000013, 425000033, 426000017, 427000001,
    428000003, 429000017, 430000013, 431000021, 432000001, 433000031, 434000053,
    435000101, 436000043, 437000021, 438000001, 439000019, 440000003, 441000023,
    442000037, 443000021, 444000041, 445000001, 446000011, 447000011, 448000013,
    449000009, 450000007, 451000009, 452000033, 453000011, 454000031, 455000023,
    456000023, 457000013, 458000033, 459000007, 460000003, 461000027, 462000017,
    463000007, 464000003, 465000037, 466000001, 467000033, 468000023, 469000003,
    470000029, 471000001, 472000007, 473000051, 474000017, 475000003, 476000029,
    477000019, 478000027, 479000017, 480000019, 481000007, 482000009, 483000029,
    484000007, 485000027, 486000007, 487000013, 488000017, 489000007, 490000001,
    491000017, 492000001, 493000007, 494000009, 495000041, 496000019, 497000039,
    498000059, 499000001, 500000003, 501000023, 502000003, 503000009, 504000011,
    505000003, 506000009, 507000001, 508000037, 509000087, 510000011, 511000019,
    512000009, 513000023, 514000001, 515000011, 516000029, 517000031, 518000009,
    519000043, 520000009, 521000021, 522000013, 523000001, 524000003, 525000031,
    526000039, 527000003, 528000017, 529000057, 530000011, 531000013, 532000009,
    533000011, 534000011, 535000007, 536000009, 537000007, 538000007, 539000027,
    540000023, 541000013, 542000071, 543000011, 544000069, 545000039, 546000001,
    547000019, 548000009, 549000013, 550000001, 551000053, 552000011, 553000009,
    554000009, 555000007, 556000001, 557000021, 558000011, 559000003, 560000011,
    561000047, 562000007, 563000041, 564000011, 565000003, 566000009, 567000011,
    568000031, 569000027, 570000023, 571000009, 572000021, 573000017, 574000027,
    575000011, 576000011, 577000001, 578000021, 579000007, 580000073, 581000087,
    582000091, 583000003, 584000003, 585000049, 586000007, 587000039, 588000001,
    589000007, 590000003, 591000017, 592000063, 593000011, 594000007, 595000001,
    596000021, 597000011, 598000009, 599000009, 600000001, 601000009, 602000029,
    603000011, 604000003, 605000003, 606000001, 607000003, 608000011, 609000001,
    610000003, 611000003, 612000001, 613000001, 614000003, 615000017, 616000009,
    617000009, 618000017, 619000009, 620000011, 621000001, 622000003, 623000033,
    624000017, 625000027, 626000041, 627000007, 628000057, 629000011, 630000013,
    631000001, 632000009, 633000013, 634000007, 635000027, 636000019, 637000009,
    638000003, 639000017, 640000019, 641000023, 642000011, 643000031, 644000009,
    645000001, 646000001, 647000017, 648000047, 649000021, 650000009, 651000011,
    652000003, 653000003, 654000059, 655000001, 656000003, 657000011, 658000003,
    659000029, 660000007, 661000009, 662000011, 663000031, 664000003, 665000027,
    666000019, 667000001, 668000009, 669000001, 670000013, 671000003, 672000011,
    673000037, 674000023, 675000037, 676000007, 677000011, 678000007, 679000019,
    680000003, 681000013, 682000001, 683000009, 684000043, 685000003, 686000009,
    687000011, 688000009, 689000027, 690000011, 691000007, 692000017, 693000073,
    694000037, 695000003, 696000013, 697000013, 698000029, 699000007, 700000001,
    701000017, 702000041, 703000013, 704000051, 705000001, 706000013, 707000003,
    708000047, 709000007, 710000021, 711000001, 712000007, 713000021, 714000011,
    715000003, 716000017, 717000001, 718000033, 719000041, 720000049, 721000009,
    722000009, 723000007, 724000007, 725000033, 726000017, 727000033, 728000003,
    729000007, 730000003, 731000087, 732000011, 733000001, 734000017, 735000001,
    736000003, 737000023, 738000001, 739000007, 740000117, 741000023, 742000013,
    743000021, 744000007, 745000007, 746000029, 747000011, 748000013, 749000033,
    750000007, 751000009, 752000089, 753000029, 754000001, 755000003, 756000103,
    757000003, 758000017, 759000017, 760000001, 761000029, 762000011, 763000003,
    764000011, 765000001, 766000003, 767000063, 768000019, 769000007, 770000009,
    771000007, 772000043, 773000021, 774000001, 775000001, 776000051, 777000001,
    778000021, 779000029, 780000017, 781000007, 782000041, 783000007, 784000001,
    785000017, 786000011, 787000099, 788000011, 789000049, 790000019, 791000011,
    792000007, 793000051, 794000003, 795000023, 796000001, 797000003, 798000023,
    799000001, 800000011, 801000007, 802000019, 803000041, 804000007, 805000019,
    806000009, 807000001, 808000003, 809000011, 810000011, 811000013, 812000023,
    813000077, 814000009, 815000029, 816000001, 817000007, 818000003, 819000023,
    820000007, 821000003, 822000017, 823000021, 824000011, 825000019, 826000003,
    827000011, 828000001, 829000013, 830000063, 831000019, 832000027, 833000041,
    834000031, 835000009, 836000003, 837000011, 838000043, 839000009, 840000017,
    841000001, 842000017, 843000007, 844000033, 845000003, 846000041, 847000009,
    848000051, 849000011, 850000013, 851000021, 852000053, 853000013, 854000009,
    855000043, 856000063, 857000057, 858000001, 859000073, 860000023, 861000013,
    862000019, 863000051, 864000001, 865000007, 866000027, 867000007, 868000033,
    869000009, 870000049, 871000001, 872000009, 873000041, 874000033, 875000033,
    876000017, 877000001, 878000009, 879000007, 880000001, 881000023, 882000013,
    883000007, 884000021, 885000007, 886000019, 887000017, 888000013, 889000001,
    890000003, 891000001, 892000003, 893000023, 894000007, 895000031, 896000003,
    897000043, 898000007, 899000017, 900000011, 901000013, 902000003, 903000001,
    904000003, 905000003, 906000037, 907000007, 908000011, 909000031, 910000031,
    911000009, 912000017, 913000021, 914000039, 915000001, 916000067, 917000023,
    918000037, 919000001, 920000021, 921000013, 922000007, 923000011, 924000013,
    925000001, 926000011, 927000001, 928000013, 929000011, 930000017, 931000001,
    932000009, 933000007, 934000007, 935000047, 936000011, 937000007, 938000003,
    939000017, 940000003, 941000029, 942000001, 943000033, 944000033, 945000013,
    946000007, 947000009, 948000007, 949000001, 950000017, 951000019, 952000009,
    953000051, 954000001, 955000027, 956000009, 957000007, 958000003, 959000071,
    960000011, 961000009, 962000023, 963000023, 964000007, 965000009, 966000017,
    967000007, 968000021, 969000023, 970000007, 971000029, 972000017, 973000033,
    974000011, 975000023, 976000013, 977000041, 978000077, 979000003, 980000023,
    981000029, 982000007, 983000023, 984000011, 985000007, 986000009, 987000017,
    988000007, 989000003, 990000023, 991000051, 992000033, 993000007, 994000037,
    995000029, 996000011, 997000007, 998000027, 999000011, 1000000007};
int main() {
  memset(isp, true, sizeof isp);
  isp[1] = false;
  for (int i = 2; i <= 5000000; i++) {
    if (isp[i]) {
      sta[++t] = i;
      for (int j = i * 2; j <= 5000000; j += i) isp[j] = false;
    }
  }
  int n;
  cin >> n;
  if (n == 3) {
    cout << "1" << endl << "3" << endl;
    return 0;
  }
  if (n == 5) {
    cout << "2" << endl << "3 2" << endl;
    return 0;
  }
  if (n > 10000019) {
    for (int i = 0;; i++) {
      if (prime[i] > n) {
        ans.push_back(prime[i - 1]);
        n -= prime[i - 1];
        break;
      }
    }
  } else {
    n -= 3;
    ans.push_back(3);
  }
  for (int i = 2; i <= n - 1; i++) {
    if (isp[i] && isp[n - i] && (i > 1) && (n - i) > 1) {
      ans.push_back(i);
      ans.push_back(n - i);
      break;
    }
  }
  cout << ans.size() << endl;
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i] << " ";
  }
  return 0;
}