数列

用以下方式构造数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。

给出一个正整数a，要求数列中第a个数对1000取模的结果是多少。

时间限制：1000

内存限制：65536

输入

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1 <= a <= 1000000)。

输出

n行，每行输出对应一个输入。输出应是一个正整数，为数列中第a个数对1000取模得到的结果。

样例输入

4
5
2
19
1

样例输出

5
1
181
1

爬楼

已知楼梯的数量，可以每次走2级或者3级，求不同的走法数

例如：楼梯一共有7级，一共3种方法：2 2 3或者 2 3 2 或者 3 2 2。

时间限制：1000

内存限制：65536

输入

输入包含若干行，每行包含一个正整数N，代表楼梯级数，1 <= N <= 50。 最后一行为0，表示测试结束。

输出

不同的走法数，每一行输入对应一行输出

样例输入

7
0

样例输出

3

井和绳子

有A, B, C, D, E五家人共用一口井，已知井深不超过k米。A, B, C, D, E的绳长各不相同，而且厘米表示的绳长一定是整数。

从井口放下绳索正好达到水面时：

(a)需要A家的绳n1条接上B家的绳1条

(b)需要B家的绳n2条接上C家的绳1条

(c)需要C家的绳n3条接上D家的绳1条

(d)需要D家的绳n4条接上E家的绳1条

(e)需要E家的绳n5条接上A家的绳1条

问井深和各家绳长。

时间限制：1000

内存限制：65536

输入

输入只有1行。包括空格分开的6个整数。 第一个整数k（1 <= k <= 20)，代表井的最大深度（单位：米）。 接下来是5个正整数n1, n2, n3, n4, n5。这五个整数的含义见上面的题目描述。

输出

输出只有1行。 如果找到了可行解，就输出6个整数，用空格分开，分别代表井的深度和A, B, C, D, E的绳长（单位都是厘米）。 如果有多组可行解，输出井的深度最小的那组解。 如果不存在可行解，就输出一行： not found

样例输入

10 2 3 4 5 6

样例输出

721 265 191 148 129 76

表达式求值

输入一个布尔表达式，请你输出它的真假值。

比如：( V | V ) & F & ( F | V )

V表示true，F表示false，&表示与，|表示或，!表示非。

上式的结果是F

时间限制：1000

内存限制：65536

输入

输入包含多行，每行一个布尔表达式，表达式中可以有空格，总长度不超过1000

输出

对每行输入，如果表达式为真，输出"V",否则出来"F"

样例输入

( V | V ) & F & ( F| V)
!V | V & V & !F & (F | V ) & (!F | F | !V & V)
(F&F|V|!V&!F&!(F|F&V))

样例输出

F
V
V

数对

给定2到15个不同的正整数，你的任务是计算这些数里面有多少个数对满足：数对中一个数是另一个数的两倍。 比如给定1 4 3 2 9 7 18 22，得到的答案是3，因为2是1的两倍，4是2个两倍，18是9的两倍。

时间限制：1000

内存限制：65536

输入

一行，给出2到15个两两不同且小于100的正整数。最后用0表示输入结束。

输出

一个整数，即有多少个数对满足其中一个数是另一个数的两倍。

样例输入

1 4 3 2 9 7 18 22 0

样例输出

3