Description
" Please don't CoCo everywhere. "
— JJ Lin, If you're not trendy, you don't have to spend money
Capybara and CabiCabi have recently made a groundbreaking discovery! The tea shop CoCo near NTHU gives you a discount coupon after every purchase, which allows you to buy an 80 NTD coffee for just 25 NTD on your next visit, and that purchase will instantly give you another coupon — they have basically found an endless loop of 25 NTD coffee!
Such unbelievably cheap prices make them unable to resist buying a cup every time they pass by. However, the cost still adds up over time, so they must come up with a more cost-effective strategy. Capybara suggested seeking help from Lizard Tom! It is rumored that Lizard Tom has recently been studying a software called "cocos creator". Although they have no idea what it is actually used for, it sounds like something capable of generating a massive amount of CoCo.
Lizard Tom has something he'd like to say: he indeed possesses the technology to create CoCo, but he has no control over the exact amount he produces.
Specifically, if CabiCabi gives him an order of cups of CoCo, the actual number of cups Lizard Tom produces will be , which is defined as follows:
L... L for Lizard! Huh? What is a function? I always predict the amount of generated CoCo by guessing!
As everyone knows, Lizard Tom is terrible at math because he never pays attention during dyy's classes. To prevent the tragedy of "CoCo everywhere" from happening, please write a program to help Capybara and CabiCabi calculate exactly how many cups of CoCo Lizard Tom will ultimately produce when they place an order for cups.
Hint
- is equivalent to , as long as there's no division in your eqution, you can take mod at anytime you want
- is SUPER BIG. You don't need to worry about large number calculations, because Python will handle it for you. But obviously, creating a list with size isn't a good idea. Furthermore, you wouldn't want to repeatedly calculate known values.
- If you revieve RE or MLE duo to Floating-point accuracy problem, try to use
//instead ofmath.floor+/
Input
The first line contains a single positive integer T, representing the number of testcases
Each testcase contains a single positive integer , representing the number of CoCo cups originally ordered from Lizard Tom.
Constraints
Subtasks
- For Testcases 1 ~ 3,
- For Testcases 4 ~ 6,
- For Testcases 7 ~ 10,
Output
For each testcase, print a single integer in a new line, representing the number of CoCo cups ultimately produced by Lizard Tom.