龙山的天气是醉人的温暖，恰好是樱花落尽的时季。散布着细沙的行人道上满是狼藉的粉色花片，有些便沾挂在平铺的碧草上。几树梨花还点缀着嫩白的残瓣。北面与西面小山上全罩着淡蓝色的衣校，小燕子来回在林中穿跳。在这里正是一年好景的残春，到处有媚丽的光景使人流连。

烟烟雾雾，云云霭霭。残春好景使人流连忘返，可是，在这伤春悲秋之时，即使柳树已经抽完了芽，青藤也换完了新枝，而鲜花已经不再盛开。明年的鲜花有，年年新花年年有，可是你曾今看到的那一朵，你永远无法挽留，即使深爱过，再也不会出现。

你引腕便要去挽，获得的只有眼角不受控落下的泪滴。你毅然步入梦中，映入眼帘的是一片开满着蓝色鸢尾花的田野。通过划分可以把这片田野化成无数块 ，第 块的面积为 个单位面积，第 块的面积为 个单位面积。每块蓝色鸢尾花田的排布以及面积如图所示：(红色数字 代表蓝色鸢尾花田编号，即第几块)



已知购买第 块蓝色鸢尾花田的一单位面积的价格 如下式所示：

现请你计算将前 片蓝色鸢尾花田全部购买下来所需要的价格。

第一行输入一个正整数   ，表示有  组测试数据。

接下来  行，每行输入只有一个正整数   ，表示要购买的是前  片蓝色鸢尾花田。

共有  行输出。

每行输出只有一个整数，表示将前  片蓝色鸢尾花田全部购买下来所需要的价格。输出可能很大，请你对  求余。

5
1
3
1
4
1314520

1
20
1
46
934267671

对于样例  ：第一块蓝色鸢尾花田的单价是  ，面积为  ，故购买前  片蓝色鸢尾花田的总价格是  。

对于样例  ：第一块蓝色鸢尾花田的单价是  ，面积为  ；第二块蓝色鸢尾花田的单价是  ，面积为  ；第三块蓝色鸢尾花田的单价是  ，面积为  。故购买前  片蓝色鸢尾花田的总价格是  。

你知道蓝色鸢尾花的花语是什么吗？ (与本题解题无关)