#![feature(wrapping)]

use std::collections::HashMap;
use std::env;
use std::fmt::Debug;
use std::hash::Hash;
use std::iter::IntoIterator;
use std::num::wrapping::OverflowingOps;
use std::ops::Index;
use std::str::FromStr;

trait IsBitData: PartialEq + Eq + Clone + Debug + Hash {
    fn empty() -> Self;
    fn set_bit(&mut self, idx: usize);
    fn get_bit(&self, idx: usize) -> bool;
    fn sub_bits(&self, from: usize, to: usize) -> Self;
}

const NUM_WORDS: usize = 2;
const WORD_LEN: usize = 64;

#[derive(PartialEq, Eq, Clone, Debug, Hash)]
struct WordVec {
    data: [u64; NUM_WORDS],
}

impl IsBitData for WordVec {
    fn empty() -> Self {
        WordVec {
            data: [0u64; NUM_WORDS],
        }
    }
    fn set_bit(&mut self, idx: usize) {
        let d = idx / WORD_LEN;
        let r = idx % WORD_LEN;
        self.data[d] |= 1u64 << r;
    }
    fn get_bit(&self, idx: usize) -> bool {
        let d = idx / WORD_LEN;
        let r = idx % WORD_LEN;
        (self.data[d] & (1u64 << r)) != 0u64
    }
    fn sub_bits(&self, from: usize, to: usize) -> Self {
        WordVec {
            data: {
                let dfrom = from / WORD_LEN;
                let rfrom = from % WORD_LEN;
                let rsfrom = (WORD_LEN - rfrom) as u32;
                let blen = to - from;
                let dlen = blen / WORD_LEN;
                let rlen = blen % WORD_LEN;
                let mut res: [u64; NUM_WORDS] = [0u64; NUM_WORDS];
                for i in (dfrom..(dfrom + dlen + 1)) {
                    if i < NUM_WORDS {
                        let from_next: u64;
                        if (i + 1) < NUM_WORDS {
                            let (from_next_v, _overflowed) = self.data[i + 1].overflowing_shl(rsfrom);
                            from_next = from_next_v;
                        } else {
                            from_next = 0u64;
                        }
                        res[i - dfrom] = (self.data[i] >> rfrom) | from_next;
                    }
                }
                res[dlen] &= (1u64 << rlen) - 1;
                res
            }
        }
    }
}

impl IsBitData for u64 {
    fn empty() -> Self {
        0u64
    }
    fn set_bit(&mut self, idx: usize) {
        *self |= 1u64 << idx;
    }
    fn get_bit(&self, idx: usize) -> bool {
        (*self & (1u64 << idx)) != 0u64
    }
    fn sub_bits(&self, from: usize, to: usize) -> Self {
        (self & ((1u64 << to) - 1)) >> from
    }
}

type BitData = WordVec;

#[derive(PartialEq, Eq, Clone, Debug, Hash)]
struct BitVec {
    bits: BitData,
    len: usize,
}

impl BitVec {
    fn new() -> BitVec {
        BitVec {
            bits: BitData::empty(),
            len: 0,
        }
    }
    fn push(&mut self, b: bool) {
        if b {
            self.bits.set_bit(self.len);
        }
        self.len += 1;
    }
    fn len(&self) -> usize {
        self.len
    }
    fn is_empty(&self) -> bool {
        self.len == 0
    }
    fn get(&self, idx: usize) -> Option<bool> {
        if idx >= self.len {
            None
        } else {
            Some(self.bits.get_bit(idx))
        }
    }
    fn sub_vec(&self, from: usize, to: usize) -> BitVec {
        BitVec {
            bits: self.bits.sub_bits(from, to),
            len: to - from,
        }
    }
}

static BF: bool = false;
static BT: bool = true;

fn static_bool(b: bool) -> &'static bool {
    match b {
        false => &BF,
        true => &BT,
    }
}

impl Index<usize> for BitVec {
    type Output = bool;
    fn index(&self, idx: usize) -> &bool {
        static_bool(self.get(idx).unwrap())
    }
}

#[derive(PartialEq, Eq, Clone, Copy, Debug, Hash)]
enum Term {
    One, Two
}

static T1: Term = Term::One;
static T2: Term = Term::Two;

fn static_term(t: Term) -> &'static Term {
    match t {
        Term::One => &T1,
        Term::Two => &T2,
    }
}

impl Term {
    fn from_bool(b: bool) -> Self {
        match b {
            false => Term::One,
            true => Term::Two,
        }
    }
    fn to_bool(self) -> bool {
        match self {
            Term::One => false,
            Term::Two => true,
        }
    }
    fn opp(self) -> Term {
        match self {
            Term::One => Term::Two,
            Term::Two => Term::One,
        }
    }
}

#[derive(PartialEq, Eq, Clone, Debug, Hash)]
struct TermList{
    bits: BitVec
}

impl TermList{
    fn new() -> TermList {
        TermList{bits: BitVec::new()}
    }
    fn push(&mut self, t: Term) {
        self.bits.push(t.to_bool());
    }
    fn len(&self) -> usize {
        self.bits.len()
    }
    fn is_empty(&self) -> bool {
        self.bits.is_empty()
    }
    fn sub_list<'a>(&'a self, from: usize, to: usize) -> TermList {
        TermList {
            bits: self.bits.sub_vec(from, to)
        }
    }
}

struct TLIter<'a> {
    tl: &'a TermList,
    place: usize,
}

impl<'a> Iterator for TLIter<'a> {
    type Item = Term;
    fn next(&mut self) -> Option<Term>{
        match self.tl.bits.get(self.place) {
            None => None,
            Some(v) => {
                self.place += 1;
                Some(Term::from_bool(v))
            },
        }
    }
}

impl <'a> IntoIterator for &'a TermList {
    type Item = Term;
    type IntoIter = TLIter<'a>;
    fn into_iter(self) -> TLIter<'a> {
        TLIter{
            tl: self,
            place: 0,
        }
    }
}

impl Index<usize> for TermList {
    type Output = Term;
    fn index<'a>(&'a self, index: usize) -> &'a Term {
        static_term(Term::from_bool(self.bits[index]))
    }
}

struct TermOps {
    term_sums: HashMap<TermList, u64>,
}

trait Parity {
    fn is_odd(&self) -> bool;
}

impl Parity for u64 {
    fn is_odd(&self) -> bool {
        (*self & 1) != 0
    }
}

impl TermOps {
    fn new() -> TermOps {
        TermOps {
            term_sums: HashMap::new()
        }
    }
    fn compute_sum_terms<'a>(&mut self, tl: &TermList) -> u64 {
        if tl.is_empty() {
            return 1;
        }
        let mut sum_count: u64 = 0;
        for piece in self.break_down(tl) {
            sum_count += self.sum_terms(&piece);
        }
        sum_count
    }
    fn sum_terms<'a>(&mut self, tl: &TermList) -> u64 {
        if !self.term_sums.contains_key(&tl) {
            let res = self.compute_sum_terms(tl);
            self.term_sums.insert(tl.clone(), res);
        }
        self.term_sums[tl]
    }
    fn count_terms(&mut self, tl: &TermList) -> u64 {
        let res = {
            if tl.is_empty() {
                0
            } else {
                self.sum_terms(&tl.sub_list(0, tl.len() - 1))
            }
        };
        res
    }
    fn next_step(&mut self, tl: &TermList) -> TermList {
        let mut res = TermList::new();
        for s in (0..tl.len()) {
            let ref subslice: TermList = tl.sub_list(0,s);
            res.push({
                let cterms = self.count_terms(&subslice);
                if cterms.is_odd(){
                    tl[s].opp()
                } else {
                    tl[s]
                }
            })
        }
        res
    }
    fn break_down<'a>(&mut self, tl: &TermList) -> Vec<TermList> {
        let tltl = tl.sub_list(1,tl.len());
        match tl[0] {
            Term::One => vec![tltl],
            Term::Two => {
                let next_tl = self.next_step(&tltl);
                vec![tltl, next_tl]
            },
        }
    }
}

fn main() {
    let mut args = env::args();
    let arg = args.nth(1).unwrap();
    let idx = u32::from_str(&arg).unwrap();
    let mut tops = TermOps::new();
    let mut sterms = TermList::new();
    for i in (1..(idx+1)) {
        sterms.push(Term::Two);
        println!("{} {}", i, tops.count_terms(&sterms));
    }
}