Submit | All submissions | Best solutions | Back to list |

## HS11SEQ - Sequences |

Given a positive integer *n*, please find all sequences of positive integers *x*_{1}, *x*_{2}, ..., *x _{k}* such that the sum of all

*k*elements of the above sequence is equal to

*n*and for each

*i*, 1<=

*i*<

*k*we have

*x*

_{i+1}-

*x*in {-2, 0, 3}.

_{i}### Input

The first line contains the number of test cases *t*. Each of the following *t* lines contains just one number 1<=*n*<=30.

### Output

For each test case print all possible sequences satisfying the problem criteria. Sequences must be given in the lexicographic order, with each sequence printed in a separate line.

### Example

Input:4 2 3 4 8Output:1 1 2 1 1 1 3 1 1 1 1 2 2 3 1 4 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 4 2 2 2 2 2 3 1 1 1 1 1 3 1 4 3 3 1 1 4 2 2 4 4 5 3 8

### Scoring

By solving this problem you score 10 points.

Added by: | kuszi |

Date: | 2012-01-15 |

Time limit: | 1s-1.875s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM32-GCC ASM64 GAWK MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SED SQLITE SWIFT UNLAMBDA VB.NET |

Resource: | High School Programming League |