问题背景

自有人类以来

不知有多少次落日时光

直到有一天，一个人面对落霞

突然“呀”了一声

人类的文明从此开始。

问题描述

在古老西方的希腊，人们采取一种奇特的方式记录日期。

第 1、2 天均用 1 表示，其后每天之日期为昨天和前天日期之和。即当$i \leq 2时$f(i)$ = 1， i > 2$时$f(i)$ = f(i - 1) + f(i - 2)。

某天落日之时，狄奥根尼手中的灯笼悄然坠落。潜滋暗长的黑暗笼罩了文明的一切痕迹——宏伟的殿堂，金色的雕塑，熙攘的人群。

“正是我的理想。”狄奥根尼（古希腊犬儒派哲学家）轻声说。他的思绪飞驰到过去的一幕幕，他蓬头赤脚逍遥自在，他像个乞丐无数次被哂笑，他希望普罗米修斯带来的东西付之一炬，他只有梦中闪现远古的呼唤。

当他的记忆来到第 $r$ 天，他希望知道第 $r$ 天的日期。

输入格式

第一行一个整数，询问次数 $n$。

之后 $n$ 行，每行一个整数 $r$ 代表第几天。

输出格式

对每次询问，输出一行一个整数，代表第 $r$ 天的日期与 $20180801$ 取余的值。“模”（余数）运算在 C/C++ 的运算符为 %。

样例

input

2
5
7

5
13

数据范围与约定

对 70% 数据，$n \leq 100, r \leq 100$。

对所有数据，$ n \leq 1000，r \leq 100000$。