package BOJ.DP;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * BOJ 9461
 * https://www.acmicpc.net/problem/9461
 */
public class WakeSequence_9461 {

    // 한계값 넣으면 int 범위 초과
    private static long[] arr = new long[100+1];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());

        arr[1] = 1;
        arr[2] = 1;
        arr[3] = 1;
        arr[4] = 2;
        arr[5] = 2;

        // P(n) : 나선에 있는 정삼각형의 변의 길이
        // P(1),P(2) ... P(10) 정도까지 나열하면 규칙을 발견할 수 있다
        // P(n) = P(n-1) + P(n-5) (n>5)
        while(testCase-- > 0){
            int n = Integer.parseInt(br.readLine());
            System.out.println(solve(n));
        }
    }

    private static long solve(int n) {
        if(arr[n] > 0)
            return arr[n];
        arr[n] = solve(n-5) + solve(n-1);
        return arr[n];
    }
}

package BOJ.DP;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


/**
 * BOJ 2748
 * https://www.acmicpc.net/problem/2748
 */
public class Fibonacci2_2748 {

    // 한계값 넣으면 int 범위 초과
    private static long[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        arr = new long[n+1];
        arr[1] = 1;
        System.out.println(fibonacci(n));

    }

    private static long fibonacci(int n){
        if(n <= 0)
            return 0;

        if(arr[n] > 0)
            return arr[n];

        arr[n] = fibonacci(n-1) + fibonacci(n-2);

        return arr[n];
    }
}

package BOJ.DP;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * BOJ 1904
 * https://www.acmicpc.net/problem/1904
 */
public class _01Tile_1904 {

    private static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        arr = new int[n+1];
        arr[0] = 1;
        arr[1] = 1;
        System.out.println(solve(n));
    }

    // D(n) : 길이가 n인 2진수열의 갯수
    // D(n)의 마지막 자리에 '00'이 오는 경우와 '1'이 오는 경우 2가지가 있다.
    // D(n) = D(n-2) + D(n-1)
    private static int solve(int n) {
        if(arr[n] > 0)
            return arr[n];

        arr[n] = solve(n-1) + solve(n-2);
        arr[n] %= 15746;
        return arr[n];

    }
}

package BOJ.DP;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * BOJ 1003
 * https://www.acmicpc.net/problem/1003
 */
public class FibonacciFunction_1003 {

    private static int[] arr = new int[40+1];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int count = Integer.parseInt(br.readLine());

        arr[0]=0;
        arr[1]=1;

        while(count-- >0){
            int n = Integer.parseInt(br.readLine());
            fibonacci(n);
            // n=0
            if(n == 0)
                System.out.println(arr[1]+" "+arr[0]);
            // n!=0 -> f(0) 호출횟수: f(n-1) / f(1) 호출횟수: f(n)
            else
                System.out.println(arr[n-1]+" "+arr[n]);
        }
    }

    private static int fibonacci(int n) {
        if(n == 0){
            return 0;
        }
        if (n == 1){
            return 1;
        }

        if(arr[n] > 0)
            return arr[n];

        arr[n] = fibonacci(n-1) + fibonacci(n-2);

        return arr[n];
    }
}

package BOJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * BOJ 9095
 * https://www.acmicpc.net/problem/9095
 */
public class OneTwoThree_9095 {

    private static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        // D(n) : n을 1,2,3의 합으로 나타낼 수 있는 경우의 수
        // 마지막 자리에 1,2,3이 오는 경우를 생각해보자.
        // 마지막 자리에 1이 온다면 D(n-1)
        // 마지막 자리에 2가 온다면 D(n-2)
        // 마지막 자리에 3이 온다면 D(n-3)
        // D(n) = D(n-1) + D(n-2) + D(n-3)
        arr = new int[10+1];

        solve();
        while(n-- >0){
            int number = Integer.parseInt(br.readLine());
            System.out.println(arr[number]);
        }
    }

    private static void solve() {
        arr[0] = 1;
        arr[1] = 1;
        arr[2] = 2;

        for(int i=3; i<11; i++){
            arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
        }
    }


}