## Problem: GCD and Fibonacci Numbers

You will be given two positive numbers M and N. Your task is to print the greatest common divisor of Fib(M) and Fib(N) where Fib(x) means the xth Fibonacci numbers defined as:

Fib(0) = 0

Fib(1) = 1

for n > 1, Fib(n) = Fib(n-1) + Fib(n-2)

Input:
The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consists of exactly one line. This line consists of two space separated positive integers N and M.

Output:

Corresponding to each test case, in a new line, print the value of gcd( Fib(M), Fib(N) ) modulo 100.

Constraints:

1 ≤ T ≤ 1000

1 ≤ M, N ≤ 1000

Example:

Input

2
3 6
7 8

Output

2
1

Explanation:

Fib(3) = 2 and Fib(6) = 8

GCD(2,8)%100 = 2

Fib(7) = 13 and Fib(8) = 21

GCD(13,21)%100 = 1

```def nth_fibo(n):
"""return the nth fibonacci number"""
if n == 0 or n == 1:
return n
n1, n2 = 0, 1
for _ in range(n):
n1, n2 = n2, n1+n2
return n1

def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)

if __name__ == '__main__':
t = input()
for _ in range(t):
a, b = map(int, raw_input().split())
print gcd(nth_fibo(a), nth_fibo(b))%100
```

## Problem: Collection of pens

Everyone have some habits to collect one thing or the other. Harshit also has the craze to collect pens but in 3 piles. In first pile, he collected A pens and in the second pile, he collected B pens but in the third and the last pile , he think of something different. He decided to collect only the minimum number of pens in third pile so that the sum of pens in the three piles will give him a prime number. Note: there should be atleast one pen in the third pile.

Input:

First line contains the test cases,t. Then T test cases follow. Each line of the test case two space separated values A,B ie. number of pens in first and
second pile respectively.

Output:
Print the minimum number of pens that should be there in the third pile so that sum of all three piles produces a prime number.

Constraints:
1&lt;=T&lt;=30
1&lt;=A&lt;=1000
1&lt;=B&lt;=1000

Example:

Input:
2
1 3
4 3

Output
1
4

Explanation:

In first case,Harshit put one pen in first pile and 3 pens in second pile which give 4 as a sum.So if he adds one pen in the third pile, the sum will yield a prime number ie.5
Similarly for other test case

Python 2.7

```from math import *
def make_primes():
sieve_eratosthenes = [True]*3001
for i in range(2, int(sqrt(len(sieve_eratosthenes)))):
if sieve_eratosthenes[i]:
temp = i+i
for j in range(temp,len(sieve_eratosthenes),i):
sieve_eratosthenes[j] = False
result = []
for i in range(2, len(sieve_eratosthenes)):
if sieve_eratosthenes[i]:
result.append(i)
return result

if __name__ == '__main__':
t = input()
primes = make_primes()
for _ in range(t):
a, b = map(int, raw_input().split())
ab = a+b
for prime in primes:
if prime > ab:
print prime-ab
break
```

## Problem: Largest number with given sum

A boy lost the password of his super locker. He remembers the number of digits N as well as the sum S of all the digits of his password. He know that his password is the largest number of N digits that can be possible with given sum S. As he is busy doing his homework, help him retrieving his password.

Input:

The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains two space separated integers N and S, where N is the number of digits in password and S is the sum of all the digits of the password.

Output:
Corresponding to each test case, in a new line, print the largest integer if possible , else print -1.

Constraints:
1<= T <= 100
1<= N <= 10000
0<= S <= 100000000

Example:

Input:

3
5 12
3 29
3 26

Output:
93000
-1
998

Explanation :

In first test case, sum of elements is 12. Largest possible 5 digit number is 93000.
In second test case, there is no such three digit number whose sum is 29.

Python 2.7

```t = input()
for _ in range(t):
n, m = [int(x) for x in raw_input().split()]
#n digits number will have max sum of its digit = n*9
if 9*n &lt; m:
print -1
else:
s = ''
if m &lt; 9:
s += str(m)
else:
s += str(9)
m -= 9
while m &gt; 0:
if m &gt;= 9:
s += str(9)
else:
s += str(m)
m -= 9
s += ('0'*(n-len(s)))
print s
```

## Problem: Mega SALE

LALU wanted to purchase a laptop so he went to a nearby sale.There were n Laptops at a sale. Laptop with index i costs ai rupees. Some Laptops have a negative price — their owners are ready to pay LALU if he buys their useless Laptop. LALU can buy any Laptop he wants. Though he’s very strong, he can carry at most m Laptops, and he has no desire to go to the sale for the second time. Please, help LALU find out the maximum sum of money that he can earn.

Input:

First line of the input contains T denoting the number of test cases.Each test case has 2 lines :

• first line has two spaced integers n m.
• second line has n integers [a0…ai…an-1].

Output:

The maximum sum of money that LALU can earn, given that he can carry at most m Laptops.
Constraints:

1≤T≤10

1≤n,m≤100

-1000≤ai≤1000
Sample Input:

1

5 3

-6 0 35 -2 4

Sample Output:

8

Explanation:

LALU takes the laptops with -6 and -2 and thus earns 8 rupees.

Python 2.7

```t = input()
for _ in range(t):
n, m = [int(x) for x in raw_input().strip().split()]
laptops = [int(x) for x in raw_input().strip().split()]
laptops.sort()
earn, amount = 0, 0
for _ in laptops:
if _ &lt;= 0:
earn += _
amount += 1
if amount == m:
break
else:
break
print earn*-1
```

## Problem: Sachin’s love for runs

Sachin always wanted to score more and more runs for his team. Sometimes he succeed in doing that and sometimes he fails.He also has a habit of noting down the runs he scored after every match in his diary. After matches he always look for his scores. In i-th match he score A[i] runs. Now he wanted to know the length of the maximum non-decreasing sub segment in sequence A. As he want to go for another match, help him in doing this task.

Input:
The first line contains T denoting the number of test cases . Then T test cases follow . The first line of each test case is an integer N . Then in the next line are N space separated values of the array A [ ] .

Output:
Print a single integer which denotes  the length of the maximum non-decreasing sub-segment.

Constraints:
1<=T<=30
1<=N<=105
1 ≤ A[ ] ≤ 109
Example:

Input
2
6
2 2 1 3 4 1
3
2 2 9

Output
3
3

Explanation

In the first test the maximum non-decreasing sub-segment is  the segment with numbers from the third to the fifth one.

In the second test the maximum non-decreasing sub-segment is the numbers from the first to the third one.

Python: 2.7

```t = input()
for _ in range(t):
n = input()
l = [int(x) for x in raw_input().strip().split()]
start, lndss, temp = l[0], 1, 1
#lnds = longest non-decreasing sub-segment
for i in range(1, len(l)):
if l[i] >= l[i-1]:
temp += 1
else:
if temp > lndss:
lndss = temp
temp = 1
if i == len(l)-1:
if temp > lndss:
lndss = temp

print lndss
```

c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r