문제
정사각형과 직사각형은 네들란드의 유명한 화가 피에트 몬드리안을 매료시켰다.
어느날, 그는 아무렇게나 생긴 영역을 정사각형과 직사각형으로
채우는 방법이 몇 개나 되는지에 흥미를 느끼게 되었다.
그는 이 문제에 전문가였기 때문에, 단번에 이 문제가 매우 어려운 것임을 알아 차렸다.
그는 이 문제를 조금 쉽게 만들기 위해 단지 두 종류의 사각형만을 사용하기로 했다.
이때 사용되는 사각형은 넓이와 높이가 모두 1인 정사각형, 그리고 넓이가 2, 높이가 1인 직사각형이다.
30분쯤 고민을 한 끝에, 그는 이 문제 역시 너무 어렵다는 것을 알아 차렸고,
문제를 풀기 위해 종이를 다 써 버렸다.
그에게 남은 종이는 화장지 밖에 없었지만,
그는 이 화장지를 정사각형과 직사각형으로 채우는 문제를 풀어 나갔다.
다행히도 화장지의 넓이는 직사각형의 넓이와 같았고,
이는 문제를 더욱 간단하게 만들어 주었다.
몇 분뒤에 그는 다음과 같은 그림을 그려내었다.
몬드리안은 이런 그림을 길이가 다른 화장지에 몇 개 더 그리기로 하였다.
그는 이 “화장실시리즈” 작품의 이름으로 정사각형과 직사각형으로
그 화장지를 채우는 방법이 몇 개인지에따라 그 수의 마지막 자리수를 사용하기로 결정하였다.
여러분이 해야할 일은 이 그림의 이름을 결정하는 프로그램을 작성하는 것이다.
입력
입력은 시리즈에 포함된 그림의 수 N ( 1≤N≤100)이 첫 행에 나타나며,
그 이후 N 개의 행이 이어진다.
하나의 행은 하나의 그림을 나타내며,
화장지의 길이를 나타내는 정수 L( 0 ≤ L ≤ 1,000,000)이 쓰여져 있다.
출력
출력은 해당하는 그림의 이름을 나타내는 숫자가 한 행씩 나타난다.
예제
5
0
1
2
3
4
1
2
7
2
1
로그인해야 코드를 작성할 수 있어요.