SNGLOOP1 - Easiest Loop 1

no tags 

Ileana D'Cruz is taking programming classes but she is having problem in understanding while loops. She is working on following set of instructions -

INTEGER I = 0, S, U = 1010;

WHILE (I < U) {
S = (3 * S) + (5 * I);
I = I + 1;
}

Let Sk be the value assigned to INTEGER S for the iteration I = (k + 1) and n, m, p be positive integers such that m > n. Ileana knows the values of n and m but she forgot the initial value of S. She is trying to find the unit digit of p. Any initial value of S may be used. She also knows the following equality -

(2 * n + 3) * (p - 1) + (4 / 5) * [(p * Sn) - Sm] = 2 * (m - n)

Input

First line of input is T (total number of test cases). Each of next T lines contains two integers n and m.

Output

Print unit digit of p (p % 10) for each test case in separated lines.

Example

Input:
1
2 3

Output:
3

Constraints

T < 10001

Explanation

Let S = 2
S0 = 6
S1 = 23
S2 = 79
S3 = 252
Now solving the equation gives p = 3.


hide comments
Rahul Jain: 2014-09-28 21:17:42

Take initial S=0 or 1, the sample test case is not satisfying.

VenkateshP: 2014-07-28 23:46:00

My O(1) algo giving TLE in Java
@Abhimanyu can you look at my submission 12041122?

Reply: Use fast IO in Java...

Last edit: 2014-09-01 00:06:22
aqfaridi: 2014-07-02 23:44:43

@Quantum : no pattern involved , just solve the given equation manually.. thats it :)

Akhil Gupta: 2014-07-02 18:18:18

Easy once you get the starting step. :D
AC in one go.

P_Quantum: 2014-06-30 20:12:02

Pattern ;)

abhay srinivas: 2014-06-29 10:42:02

observing pattern for sn is the key!!

Ravi Shankar Mondal: 2014-06-21 01:05:44

cakewalk

Koderok: 2014-06-20 12:05:46

What are the limits on n and m?
Edit: Limits on m and n don't matter. I got AC using 4 byte integers. Awesome problem!

Last edit: 2014-06-20 12:19:13
Sam Winchester: 2014-06-19 14:55:32

Same code getting AC in C in 0.03 and TLE in JAVA !!! Why ??

Last edit: 2014-06-19 14:56:39

Added by:AvmnuSng
Date:2014-06-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Abhimanyu Singh
My Problems