CRZYSMKR - Crazy Smoker


The "BHAI Group" Of IIIT Allahabad is Famous For Many Things, Leading in Every Field Of College Activity

So One Day The Leader Of Bhai Group decided to smoke C(N) cigarettes each day:

- F(N) = 34^N+ (30 x N) + 32

- C(N) = F(N) mod (11), where x mod y is the remainder obtained by dividing x by y.

But Bhai Group's Leader's Girlfriend wants that he doesn't smoke any cigarette, so she made modifications:

- F(N) = 34^N+ (30 x N) + (32 + M)

- C(N) = F(N) mod (11)

Edit 1 : Time limit set to 0.100s

Problem Credits : IIIT Allahabad HE Club

Input

First line of each test case is an integer T, total number of test cases. Next T lines contains a single integer N.

Output

Print the minimum value of M in single line for each test case.

Constraints

1 <= T <= 10^6

1 <= N <= 10^18

Example

Input:
2
1
2

Output:
3
6
Explanation:
For N = 1
F(N) = 34 + 30 + 32 = 96
So, M = 3
Now, C(N) = 99 mod(11) = 0
For N = 2
F(N) = 1156 + 60 + 32 = 1248
So, M = 6
Now, C(N) = 1254 mod(11) = 0

hide comments
dragonfly_07: 2016-07-25 22:47:31

easy one ...but nice mathematics is involved
try to break the problem into parts

gaurav_07: 2016-07-13 07:33:23

nice question

iharsh234: 2016-07-12 22:22:48

Here comes my century!!
2 lines of python is enough!

vineetpratik: 2016-06-21 19:00:40

done it without any modular exponentiation , simple concept of binomial expansion :) gives you a linear equation to check :D

SUBHAJIT GORAI: 2016-05-15 08:32:40

Thanks @Murad Al Wajed ,I too made the same mistake and it costed me two WA's . :)

Murad Al Wajed: 2016-04-24 10:59:57

when C(N)= 0 result will 0. This shit cost me 4 WA

suman_biswas95: 2016-03-01 10:27:38

this is awesome......

Abhishek Kumar Singh: 2016-02-20 06:53:22

For those who know Remainder theorem, this is a 6 line code in C/C++.

Ankit: 2016-02-19 19:59:32

This was mathematics. :D Got it in the 2nd attmept. :)

pvkcse: 2016-02-17 18:24:04

@divyanshu01 yes there is... haven't you heard about pow() in python with three arguments?
pow(base,exp,modulus). Hope it helps!
@Farhan764 Thanks!! you saved me from more WA's!

Last edit: 2016-02-17 18:25:52

Added by:Siddharth Singh
Date:2016-02-10
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:HackerEarth Contest Of IIIT Allahabad