Little Gaurav is very fond of numbers and sequences. One day his teacher tells him to find a strange sequence.
\[S = \sum\limits_{i=0, 2^i\leq n}^{\infty}\sum\limits_{j=0}^n 2^{2^i+2j}\]
Since this sequence looks a bit difficult, the teacher tells him to find the last digit of \(S\).
Little Gaurav is confused because he cannot solve the problem and leaves this problem to the worthy programmers of the world. Help little Gaurav in finding the solution.
Input Format
The first line contains \(T\), the number of test cases.
\(T\) lines follow, each line containing an integer, \(N\).
Output Format
For each testcase, print the last digit of \(S\) in one line.
Constraints
\(1\leq T\leq 1000\)
\(1\leq N\leq 10^{15}\)
Sample Input
3
1
2
3
Sample Output
0
6
0
Explanation
For n=1, only i=0 is valid. So \(S\) is \(2^{2^0+0}+2^{2^0+2}=10\). Hence last digit of S is 0.
For n=2, only i=0 and 1 are valid. So S is
S1(for i=0) is \(2^{2^0+0}+2^{2^0+2}+2^{2^0+4}=42\).
S2(for i=1) is \(2^{2^1+0}+2^{2^1+2}+2^{2^1+4}=84\).
So last digit of S is 6.
Solution
Since we want to find the last digit only, we can work out the solution under a modular congruence relation modulo 10:
\[S \equiv \sum\limits_{i=0, 2^i\leq n}^{\infty}\sum\limits_{j=0}^n 2^{2^i+2j} \pmod{10}\]
Since the way the way the upper bound is defined is a little uncommon, we rewrite the outer sum as well as the exponential:
\[S \equiv \sum\limits_{i=0}^{\lfloor\log_2 n\rfloor}\sum\limits_{j=0}^n 2^{2^i}2^{2j} \pmod{10}\]
The inner sum has a constant factor, which can be brought to the front. Then the inner sum remains with \(2^{2j}=4^j\):
\[S \equiv \sum\limits_{i=0}^{\lfloor\log_2 n\rfloor}2^{2^i}\sum\limits_{j=0}^n 4^{j} \pmod{10}\]
The inner sum now has a well known closed form solution:
\[S \equiv \sum\limits_{i=0}^{\lfloor\log_2 n\rfloor}2^{2^i} \frac{1}{3}(4^{n+1}-1) \pmod{10}\]
We can now make use of the congruence relation and remove the \(\frac{1}{3}\) with the modular inverse.
\[S \equiv \sum\limits_{i=0}^{\lfloor\log_2 n\rfloor}2^{2^i} \cdot 7(4^{n+1}-1) \pmod{10}\]
Moving the 7 into the brackets gives us a -7, which is 3 under modulo 10 and \(7\cdot 4^{n+1}\), which is 2 for n being odd and 8 for n being even. The formal inner sum doesn't depend on the outer loop, so we can move it out:
\[S \equiv \left(3 + \begin{cases} 2,& \text{if } n \text{ odd}\\ 8,& \text{else} \end{cases}\right) \sum\limits_{i=0}^{\lfloor\log_2 n\rfloor}2^{2^i} \pmod{10}\]
Adding the 3 under modulo 10 gives:
\[S \equiv \left(\begin{cases} 5,& \text{if } n \text{ odd}\\ 1,& \text{else} \end{cases}\right) \sum\limits_{i=0}^{\lfloor\log_2 n\rfloor}2^{2^i} \pmod{10}\]
Okay, we still have the right sum over the power of twos and I think there is no closed form solution for it. However, we work under the modular congruence and can see if there are some patterns. Let's say \(m=\lfloor\log_2 n\rfloor\). When we look into \(2^{2^i} \pmod{10}\), we notice, that the result is always 6, except for i=0 and i=1 where it is 2 and 4 respectively. That means that we simply have to add \(2+4\) and another \(m-1\) times 6. That said
\[\sum\limits_{i=0}^{m}2^{2^i}\equiv \underbrace{2+4 + 6(m-1)}_{=6m} \pmod{10}\]
This holds for all \(m>0\), but we still have one special case. For \(m=0\) we should get \(2^{2^0}=2\) but \(2m\) is 0. Okay let's bring this to Ruby code:
gets.to_i.times{
n = gets.to_i
m = Math.log2(n).floor()
k = m == 0 ? 2 : 6 * m
puts [1, 5][n % 2] * k % 10
}
Okay, since we have only two cases for the first factor, we can obfuscate the code a bit more. In order to pass all tests on hackerrank, we don't need to check for the special case, so
gets.to_i.times{
n = gets.to_i
m = Math.log2(n).floor()
p 6 * m * (1 + n % 2 * 4) % 10
}