UOJ Logo LFYZ Online Judge

LFYZOJ

#307. 落照(sunset)

统计

问题背景

自有人类以来

不知有多少次落日时光

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

突然“呀”了一声

人类的文明从此开始。

问题描述

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

第 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
#### output
5
13

数据范围与约定

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

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