annum

Mar 20, 2009, 12:23 PM

QUESTION 1 -

The Prime Numbers

MishraJi, a mathematics teacher, was teaching his 6th standard students about the prime

numbers. He listed the first 15 prime numbers on the blackboard:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

"We see that the 13th prime number is 41.", said MishraJi. Little Tinku, fascinated about the

prime numbers, asked, "Sir, what is the 100th prime number?" The teacher, unable to answer the

question then, promised Tinku to tell the answer in the next class.

Task

Your task is to help MishraJi by writing a program which can tell the Nth prime number.

Input

The first line of the input will contain the single positive integer t (1 <= t <= 1000), indicating

the number of test cases to follow. The following t lines will be containing one positive integer n

per line (1<= n <= 100000).

Output

The output will consist of t lines, with exactly one number on each line, the n-th prime number.

Example

Sample input:

3

13

100

10001

Sample output:

41

541

104743

Marks : 20

Time Limit : 3 seconds

question 2

The Palindromes

A string is said to be palindrome, if it reads same from both ends, i.e, from left-to-right and from

right-to-left. For example, “MALAYALAM” is a palindrome string. The letters are symmetrical at

both ends.

Similarly, a numeral palindrome has corresponding digits from the both ends symmetrical. So, on

reversing the digits of the number, we get the same number itself. Thus, 23432 is a palindrome

number. Further, some numbers have the property that they are palindrome in both decimal, and

binary bases. One such example is the number 58510 = 10010010012

We see that both 585 and 1001001001 are palindromes.

Task

In a given range, you have to find out those numbers which are palindrome in both decimal and

binary bases, and report their decimal sum.

Input

The first line of the input will have a single integer t (1 <= t <= 50), the number of test cases. Then,

t test cases will follow. Each test case will consist of two numbers m and n, which will define the

lower limit and the upper limit of the range (m, n <= 10000000 and m < n).

Output

The output will contain t lines with exactly one number on each line, the sum of all the palindromes

(in both decimal and binary bases) that lie in the given range [m, n].

Examples

Sample input:

3

1 100

300 1000

10000 50000

Sample output:

157

1772

89339

Marks : 20

Time Limit : 3 seconds

question 3

The Language War

Apologists of Java and C++ can argue for hours proving each other that their programming

language is the best one. Java people will tell that their programs are clearer and less prone to

errors, while C++ people will laugh at their inability to instantiate an array of generics or tell them

that their programs are slow and have long source code.

Another issue that Java and C++ people could never agree on is identifier naming. In Java a

multiword identifier is constructed in the following manner: the first word is written starting from

the small letter, and the following ones are written starting from the capital letter, no separators are

used. All other letters are small. Examples of a Java identifier are javaIdentifier,

longAndMnemonicIdentifier, name, nEERC.

Unlike them, C++ people use only small letters in their identifiers. To separate words they use

underscore character ‘_’. Examples of C++ identifiers are c_identifier,

long_and_mnemonic_identifier, name (you see that when there is just one word Java and C++

people agree), n_e_e_r_c.

You are writing a translator that is intended to translate C++ programs to Java and vice versa. Of

course, identifiers in the translated program must be formatted due to its language rules —

otherwise people will never like your translator.

Task

The first thing you would like to write is an identifier translation routine. Given an identifier, it

would detect whether it is Java identifier or C++ identifier and translate it to another dialect. If it is

neither, then your routine should report an error. Translation must preserve the order of words and

must only change the case of letters and/or add/remove underscores.

Input

The input file consists of several lines that contains an identifier. It consists of letters of the English

alphabet and underscores. Its length does not exceed 100.

Output

If the input identifier is Java identifier, output its C++ version. If it is C++ identifier, output its Java

version. If it is none, output 'Error!' instead.

Example

Sample Input:

the_holy_war_of_languages

anotherExample

input

bad_Style

Sample Output:

theHolyWarOfLanguages

another_example

input

Error!

Marks : 35

Time Limit : 3 seconds

question 3

The Language War

Apologists of Java and C++ can argue for hours proving each other that their programming

language is the best one. Java people will tell that their programs are clearer and less prone to

errors, while C++ people will laugh at their inability to instantiate an array of generics or tell them

that their programs are slow and have long source code.

Another issue that Java and C++ people could never agree on is identifier naming. In Java a

multiword identifier is constructed in the following manner: the first word is written starting from

the small letter, and the following ones are written starting from the capital letter, no separators are

used. All other letters are small. Examples of a Java identifier are javaIdentifier,

longAndMnemonicIdentifier, name, nEERC.

Unlike them, C++ people use only small letters in their identifiers. To separate words they use

underscore character ‘_’. Examples of C++ identifiers are c_identifier,

long_and_mnemonic_identifier, name (you see that when there is just one word Java and C++

people agree), n_e_e_r_c.

You are writing a translator that is intended to translate C++ programs to Java and vice versa. Of

course, identifiers in the translated program must be formatted due to its language rules —

otherwise people will never like your translator.

Task

The first thing you would like to write is an identifier translation routine. Given an identifier, it

would detect whether it is Java identifier or C++ identifier and translate it to another dialect. If it is

neither, then your routine should report an error. Translation must preserve the order of words and

must only change the case of letters and/or add/remove underscores.

Input

The input file consists of several lines that contains an identifier. It consists of letters of the English

alphabet and underscores. Its length does not exceed 100.

Output

If the input identifier is Java identifier, output its C++ version. If it is C++ identifier, output its Java

version. If it is none, output 'Error!' instead.

Example

Sample Input:

the_holy_war_of_languages

anotherExample

input

bad_Style

Sample Output:

theHolyWarOfLanguages

another_example

input

Error!

Marks : 35

Time Limit : 3 seconds

question 4

Maximum Sub-Array

For an array of n integers, the maximum sub-array can be defined as that subset of consecutive

elements of the array, which on addition, yield the maximum sum. For example, if there is an array

A = {8, -10, 7, 4, -3, 5, -9, 2, -4, 3 } ,

then the maximum sub-array whose elements add up to produce maximum sum is { 7, 4, -3, 5 }

with the sum being 13.

Task

Given a set of arrays, your task is to find out their respective maximum sub-arrays, and report the

sum of the elements of each sub-array

Input

The first line of the input will be a positive integer t (1 <= t <= 100000). t lines will follow

representing each of the t test cases. Each of these lines will contain 25 integers, the elements of

each array.

Output

The output should be of t lines, with exactly one number on each line, the sum of the elements of

the corresponding array's maximum sub-array.

Example

Sample input:

3

8 20

22 97

38

15 0 40 0 75 4 50

7 78

52 12 50

77 91 80

49 49

99 40

17

18

8 57 60

87 17 40 98 43

69 48 4

56 62 0 81 49

31 73

55

79 14

29 93

7

40 67 53 88

30 3 49

13 36 65

52 70

95 23

4

60 11

42 69

24 68 56 1 32

5

Sample output:

214

516

261

Marks : 35

Time Limit : 3 seconds

question 5

Number Pyramid

A number pyramid is a set of numbers arranged in the form of a pyramid. An example of one such

pyramid of height 5 is

99

23 75

80 11 34

15 40 72 15

42 84 93 15 66

On travelling down the pyramid from top to bottom, one has to step down either on the left-handside

number or the right-hand-side number from the current number. So, mathematically, if the

height of the pyramid is n, there can be 2n (2 raised to the power n) different paths possible to reach

from the top to the bottom. Out of these 2n paths, the highest-valued path is defined as that path

whose elements produce the maximum total. For example, the highest-valued path in the above

pyramid is

99

23 75

80 11 34

15 40 72 15

42 84 93 15 66

with the sum being 99 + 75 + 34 + 72 + 93 = 343.

Task

For a given set of such pyramids, your task is to find the highest-valued path for each pyramid, and

report the sum.

Input

The first line of the input will be a positive integer t (1 <= t <= 10000), the number of test cases.

Afterwards, t test cases will follow. The input pattern for each test case will be as following:

The first line will contain one positive number n (1 <= n <= 20), the height of the pyramid. After

this, n lines will follow. For each i (1 <= i <= n), the i-th line will contain i numbers, the elements

of that line in the number pyramid.

Output

The output will consist of t lines, with each line having exactly one number, the sum of the highestvalued

path of the corresponding pyramid.

Example

Sample input:

3

3

5

2 3

9 7 1

4

68

23 90

45 23 76

10 95 34 26

5

95

35 13

14 76 34

09 23 16 74

33 67 21 76 25

Sample output:

16

276

298

Marks : 35

Time Limit : 2 seconds

question 5

Factorials

In mathematics there is the concept of the factorial of a number. They are symbolised like this n!,

pronounced n factorial ( or factorial n). 9! is nine factorial (or factorial nine). The factorial of an

integer is the product of all the positive integers less than or equal to it. Factorials get large very

rapidly. The factorial of 13 is !13 = 1*2*3*4*5*6*7*8*9*10*11*12*13 = 6227020800. This

number already exceeds what can be fit into a 32-bit integer. Obviously, calculating factorials of

large numbers isn't very easy. But, that's what computers are for, to do the cumbersome numbercrunching,

so that we don't have to do it ourselves!

Task

Your task is to write a program that computes the factorials of 3-digit numbers. But, as I don't like

that huge numbers unless they are on my paycheck, ofcourse, I'll be happy if you just print the sum

of the digits of the factorial you find.

Input

As usual, the first line of the input will contain a single integer t (1 <= t <= 500), the number of test

cases. Following it will be t lines, all containing a single positive integer n (1 <= n <= 999).

Output

The output will contain t lines, with one number on each line, the sum of the digits of the factorial

of the corresponding number n.

Example

Sample input:

4

13

42

100

666

Sample output:

27

189

648

6327

Marks : 50

Time Limit : 3 seconds

question 6

Factorials

In mathematics there is the concept of the factorial of a number. They are symbolised like this n!,

pronounced n factorial ( or factorial n). 9! is nine factorial (or factorial nine). The factorial of an

integer is the product of all the positive integers less than or equal to it. Factorials get large very

rapidly. The factorial of 13 is !13 = 1*2*3*4*5*6*7*8*9*10*11*12*13 = 6227020800. This

number already exceeds what can be fit into a 32-bit integer. Obviously, calculating factorials of

large numbers isn't very easy. But, that's what computers are for, to do the cumbersome numbercrunching,

so that we don't have to do it ourselves!

Task

Your task is to write a program that computes the factorials of 3-digit numbers. But, as I don't like

that huge numbers unless they are on my paycheck, ofcourse, I'll be happy if you just print the sum

of the digits of the factorial you find.

Input

As usual, the first line of the input will contain a single integer t (1 <= t <= 500), the number of test

cases. Following it will be t lines, all containing a single positive integer n (1 <= n <= 999).

Output

The output will contain t lines, with one number on each line, the sum of the digits of the factorial

of the corresponding number n.

Example

Sample input:

4

13

42

100

666

Sample output:

27

189

648

6327

Marks : 50

Time Limit : 3 seconds

please solve this question immediatly i need this answer within 3 hr .

The Prime Numbers

MishraJi, a mathematics teacher, was teaching his 6th standard students about the prime

numbers. He listed the first 15 prime numbers on the blackboard:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

"We see that the 13th prime number is 41.", said MishraJi. Little Tinku, fascinated about the

prime numbers, asked, "Sir, what is the 100th prime number?" The teacher, unable to answer the

question then, promised Tinku to tell the answer in the next class.

Task

Your task is to help MishraJi by writing a program which can tell the Nth prime number.

Input

The first line of the input will contain the single positive integer t (1 <= t <= 1000), indicating

the number of test cases to follow. The following t lines will be containing one positive integer n

per line (1<= n <= 100000).

Output

The output will consist of t lines, with exactly one number on each line, the n-th prime number.

Example

Sample input:

3

13

100

10001

Sample output:

41

541

104743

Marks : 20

Time Limit : 3 seconds

question 2

The Palindromes

A string is said to be palindrome, if it reads same from both ends, i.e, from left-to-right and from

right-to-left. For example, “MALAYALAM” is a palindrome string. The letters are symmetrical at

both ends.

Similarly, a numeral palindrome has corresponding digits from the both ends symmetrical. So, on

reversing the digits of the number, we get the same number itself. Thus, 23432 is a palindrome

number. Further, some numbers have the property that they are palindrome in both decimal, and

binary bases. One such example is the number 58510 = 10010010012

We see that both 585 and 1001001001 are palindromes.

Task

In a given range, you have to find out those numbers which are palindrome in both decimal and

binary bases, and report their decimal sum.

Input

The first line of the input will have a single integer t (1 <= t <= 50), the number of test cases. Then,

t test cases will follow. Each test case will consist of two numbers m and n, which will define the

lower limit and the upper limit of the range (m, n <= 10000000 and m < n).

Output

The output will contain t lines with exactly one number on each line, the sum of all the palindromes

(in both decimal and binary bases) that lie in the given range [m, n].

Examples

Sample input:

3

1 100

300 1000

10000 50000

Sample output:

157

1772

89339

Marks : 20

Time Limit : 3 seconds

question 3

The Language War

Apologists of Java and C++ can argue for hours proving each other that their programming

language is the best one. Java people will tell that their programs are clearer and less prone to

errors, while C++ people will laugh at their inability to instantiate an array of generics or tell them

that their programs are slow and have long source code.

Another issue that Java and C++ people could never agree on is identifier naming. In Java a

multiword identifier is constructed in the following manner: the first word is written starting from

the small letter, and the following ones are written starting from the capital letter, no separators are

used. All other letters are small. Examples of a Java identifier are javaIdentifier,

longAndMnemonicIdentifier, name, nEERC.

Unlike them, C++ people use only small letters in their identifiers. To separate words they use

underscore character ‘_’. Examples of C++ identifiers are c_identifier,

long_and_mnemonic_identifier, name (you see that when there is just one word Java and C++

people agree), n_e_e_r_c.

You are writing a translator that is intended to translate C++ programs to Java and vice versa. Of

course, identifiers in the translated program must be formatted due to its language rules —

otherwise people will never like your translator.

Task

The first thing you would like to write is an identifier translation routine. Given an identifier, it

would detect whether it is Java identifier or C++ identifier and translate it to another dialect. If it is

neither, then your routine should report an error. Translation must preserve the order of words and

must only change the case of letters and/or add/remove underscores.

Input

The input file consists of several lines that contains an identifier. It consists of letters of the English

alphabet and underscores. Its length does not exceed 100.

Output

If the input identifier is Java identifier, output its C++ version. If it is C++ identifier, output its Java

version. If it is none, output 'Error!' instead.

Example

Sample Input:

the_holy_war_of_languages

anotherExample

input

bad_Style

Sample Output:

theHolyWarOfLanguages

another_example

input

Error!

Marks : 35

Time Limit : 3 seconds

question 3

The Language War

Apologists of Java and C++ can argue for hours proving each other that their programming

language is the best one. Java people will tell that their programs are clearer and less prone to

errors, while C++ people will laugh at their inability to instantiate an array of generics or tell them

that their programs are slow and have long source code.

Another issue that Java and C++ people could never agree on is identifier naming. In Java a

multiword identifier is constructed in the following manner: the first word is written starting from

the small letter, and the following ones are written starting from the capital letter, no separators are

used. All other letters are small. Examples of a Java identifier are javaIdentifier,

longAndMnemonicIdentifier, name, nEERC.

Unlike them, C++ people use only small letters in their identifiers. To separate words they use

underscore character ‘_’. Examples of C++ identifiers are c_identifier,

long_and_mnemonic_identifier, name (you see that when there is just one word Java and C++

people agree), n_e_e_r_c.

You are writing a translator that is intended to translate C++ programs to Java and vice versa. Of

course, identifiers in the translated program must be formatted due to its language rules —

otherwise people will never like your translator.

Task

The first thing you would like to write is an identifier translation routine. Given an identifier, it

would detect whether it is Java identifier or C++ identifier and translate it to another dialect. If it is

neither, then your routine should report an error. Translation must preserve the order of words and

must only change the case of letters and/or add/remove underscores.

Input

The input file consists of several lines that contains an identifier. It consists of letters of the English

alphabet and underscores. Its length does not exceed 100.

Output

If the input identifier is Java identifier, output its C++ version. If it is C++ identifier, output its Java

version. If it is none, output 'Error!' instead.

Example

Sample Input:

the_holy_war_of_languages

anotherExample

input

bad_Style

Sample Output:

theHolyWarOfLanguages

another_example

input

Error!

Marks : 35

Time Limit : 3 seconds

question 4

Maximum Sub-Array

For an array of n integers, the maximum sub-array can be defined as that subset of consecutive

elements of the array, which on addition, yield the maximum sum. For example, if there is an array

A = {8, -10, 7, 4, -3, 5, -9, 2, -4, 3 } ,

then the maximum sub-array whose elements add up to produce maximum sum is { 7, 4, -3, 5 }

with the sum being 13.

Task

Given a set of arrays, your task is to find out their respective maximum sub-arrays, and report the

sum of the elements of each sub-array

Input

The first line of the input will be a positive integer t (1 <= t <= 100000). t lines will follow

representing each of the t test cases. Each of these lines will contain 25 integers, the elements of

each array.

Output

The output should be of t lines, with exactly one number on each line, the sum of the elements of

the corresponding array's maximum sub-array.

Example

Sample input:

3

8 20

22 97

38

15 0 40 0 75 4 50

7 78

52 12 50

77 91 80

49 49

99 40

17

18

8 57 60

87 17 40 98 43

69 48 4

56 62 0 81 49

31 73

55

79 14

29 93

7

40 67 53 88

30 3 49

13 36 65

52 70

95 23

4

60 11

42 69

24 68 56 1 32

5

Sample output:

214

516

261

Marks : 35

Time Limit : 3 seconds

question 5

Number Pyramid

A number pyramid is a set of numbers arranged in the form of a pyramid. An example of one such

pyramid of height 5 is

99

23 75

80 11 34

15 40 72 15

42 84 93 15 66

On travelling down the pyramid from top to bottom, one has to step down either on the left-handside

number or the right-hand-side number from the current number. So, mathematically, if the

height of the pyramid is n, there can be 2n (2 raised to the power n) different paths possible to reach

from the top to the bottom. Out of these 2n paths, the highest-valued path is defined as that path

whose elements produce the maximum total. For example, the highest-valued path in the above

pyramid is

99

23 75

80 11 34

15 40 72 15

42 84 93 15 66

with the sum being 99 + 75 + 34 + 72 + 93 = 343.

Task

For a given set of such pyramids, your task is to find the highest-valued path for each pyramid, and

report the sum.

Input

The first line of the input will be a positive integer t (1 <= t <= 10000), the number of test cases.

Afterwards, t test cases will follow. The input pattern for each test case will be as following:

The first line will contain one positive number n (1 <= n <= 20), the height of the pyramid. After

this, n lines will follow. For each i (1 <= i <= n), the i-th line will contain i numbers, the elements

of that line in the number pyramid.

Output

The output will consist of t lines, with each line having exactly one number, the sum of the highestvalued

path of the corresponding pyramid.

Example

Sample input:

3

3

5

2 3

9 7 1

4

68

23 90

45 23 76

10 95 34 26

5

95

35 13

14 76 34

09 23 16 74

33 67 21 76 25

Sample output:

16

276

298

Marks : 35

Time Limit : 2 seconds

question 5

Factorials

In mathematics there is the concept of the factorial of a number. They are symbolised like this n!,

pronounced n factorial ( or factorial n). 9! is nine factorial (or factorial nine). The factorial of an

integer is the product of all the positive integers less than or equal to it. Factorials get large very

rapidly. The factorial of 13 is !13 = 1*2*3*4*5*6*7*8*9*10*11*12*13 = 6227020800. This

number already exceeds what can be fit into a 32-bit integer. Obviously, calculating factorials of

large numbers isn't very easy. But, that's what computers are for, to do the cumbersome numbercrunching,

so that we don't have to do it ourselves!

Task

Your task is to write a program that computes the factorials of 3-digit numbers. But, as I don't like

that huge numbers unless they are on my paycheck, ofcourse, I'll be happy if you just print the sum

of the digits of the factorial you find.

Input

As usual, the first line of the input will contain a single integer t (1 <= t <= 500), the number of test

cases. Following it will be t lines, all containing a single positive integer n (1 <= n <= 999).

Output

The output will contain t lines, with one number on each line, the sum of the digits of the factorial

of the corresponding number n.

Example

Sample input:

4

13

42

100

666

Sample output:

27

189

648

6327

Marks : 50

Time Limit : 3 seconds

question 6

Factorials

In mathematics there is the concept of the factorial of a number. They are symbolised like this n!,

pronounced n factorial ( or factorial n). 9! is nine factorial (or factorial nine). The factorial of an

integer is the product of all the positive integers less than or equal to it. Factorials get large very

rapidly. The factorial of 13 is !13 = 1*2*3*4*5*6*7*8*9*10*11*12*13 = 6227020800. This

number already exceeds what can be fit into a 32-bit integer. Obviously, calculating factorials of

large numbers isn't very easy. But, that's what computers are for, to do the cumbersome numbercrunching,

so that we don't have to do it ourselves!

Task

Your task is to write a program that computes the factorials of 3-digit numbers. But, as I don't like

that huge numbers unless they are on my paycheck, ofcourse, I'll be happy if you just print the sum

of the digits of the factorial you find.

Input

As usual, the first line of the input will contain a single integer t (1 <= t <= 500), the number of test

cases. Following it will be t lines, all containing a single positive integer n (1 <= n <= 999).

Output

The output will contain t lines, with one number on each line, the sum of the digits of the factorial

of the corresponding number n.

Example

Sample input:

4

13

42

100

666

Sample output:

27

189

648

6327

Marks : 50

Time Limit : 3 seconds

please solve this question immediatly i need this answer within 3 hr .