CRZYSMKR - Crazy Smoker


 

The "BHAI Group" Of Every College is Famous For Many Things.
So One Day The Leader Of Bhai Group decided to smoke **C(N)** cigarettes each day:
 - **F(N) = 34<sup>N</sup> + (30 x N) + 32**
 - **C(N) = F(N) mod (11)**, where **x mod (y)** is the remainder obtained by diving 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<sup>N</sup> + (30 x N) + (32 + M)**
 - **C(N) = F(N) mod (11)**
**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**<br>
<b>
 - 1 <= T <= 10<sup>6</sup>
 - 1 <= N <= 10<sup>18</sup>
</b>

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 diving 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 .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
Explaination :
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
Robert Gawron: 2018-12-29 10:46:38

No need to calculate 34^N, because 34^N % 11 is always 1 and (a+b+c)%N = a%N +b%N +c%N

bansalabhi_98: 2018-06-19 12:48:19

nice mathematics

anirudnits: 2018-02-22 11:55:35

Don't believe spojtoolkit for this one.

monil_ladha: 2017-12-05 13:14:04

Super easy, just follow modular arithmetic closely!!

Last edit: 2017-12-05 13:15:05
code_block: 2017-05-28 20:10:00

AC in a GO!!
Just the Binomial Expansion....and its done!!

sudeep_11: 2017-02-02 15:36:55

those who know binomial expansion can do it in easily !

shubham_cs_iet: 2017-01-06 11:59:33

34^(10^18) is beyond C limits, costed me 2 WA.

Shashank Tiwari: 2016-11-01 13:07:47

Let me simplify the stupid problem statement :

Find minimum non negative 'M' such that

(34^N + 30*N + 32 +M )%11 = 0

Last edit: 2016-11-01 13:08:38
monish007: 2016-08-18 13:57:20

Sily Mistake cost me 2 WA .. otherwise should be moved in basics too easy

somya_v: 2016-07-30 08:51:15

observe the pattern..:D


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