Test ur C-Skills a complex c questions to satisfy ur thirsty guys

1. COUNTRY CODE
Consider every country being assigned a unique 4 digit code by the United Nations for security purposes.
The presidents of several countries are now quite upset by the message from the GM of the UN stating that they would all have to change their corresponding four-digit country codes.An excerpt from a conversation between the GM and the presidents:
— These codes have to be changed often for security.
— But look, I have chosen my number 1033 for good reasons. I am the President of the US, you know!
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones.
— Not that easy. If I change the first digit to an 8, then the number will be 8033 which is not a prime!
— hmmm.....being the president you cannot stand having a non-prime number as your code even for a few seconds.±±
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.

Now, the President of Pakistan, who had been eavesdropping, intervened.
— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound.
— Hmm, in that case I need a computer program to minimize the cost. You don't know some very cheap software gurus, do you?
— In fact, I do. You see, there is this programming contest going on...

Help the President to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.
1033

1733

3733

3739

3779

8779

8179

The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.

Input

One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros).

Output

One line for each case, either with a number stating the minimal cost or containing the word Impossible.

Example

Input:

3

1033 8179

1373 8017

1033 1033


Output:
6
7
0


2. BASE STATION
In the context of wireless communication, an input contains several situations. A data set containing two numbers F and G (integers) marks the beginning of each situation. F is the number of points of interest,1 <= F <= 2 000. G is the maximal range the BTS (Base Station) is able to cover, 0 <= G < 10 000. Then there are F data sets, each containing two integer numbers M_i, N_i giving coordinates of the i-th point, |M_i|, |N_i| < 10 000. All points are unique i.e., no two of them will have the same coordinates.

The situation is followed by one empty data set and then the next situation begins. The last one is followed by a dataset containing two zeros.

A point on the circular boundary (exactly in the distance G) is covered. . The input points are always selected in such a way that for any possible subset of points S that can be covered by a circle with the radius G +0.001, there will always exist a circle with the radius G that also covers them.

Output
For each situation, print a data set containing the sentence "It is possible to cover Y points.", where Y is the maximal number of points of interest that may be covered by a single BTS.



Example
Input:


8 2
1 2
5 3
5 4
1 4
8 2
4 5
7 5
3 3


2 100
0 100
0 -100


0 0


Output:


It is possible to cover 4 points.
It is possible to cover 2 points.


3. WORD SEARCH PUZZLE
You are given an n*n array of characters and a word. Write a program to spot the word in the array, when read horizontally, vertically or diagonally (forward or reverse). For example, the following array of characters contains the words: queue, hunt, help, lakh, lens, peel, keep, at, tight, the, etc.




a
h
k
A
l
q
u
e
U
e
s
n
e
L
e
a
t
p
H
p
t
h
g
I
t
Input:
5
a h k A l
q u e U e
s n e L e
a t p H p
t h g I t
peel pen
Output: YES Output: NO



4. SOUNDEX INDEX SYSTEM
The Soundex Index System was developed so that similarly sounding names or names with similar spelling could be encoded for easy retrieval. It has been used by the U.S. Bureau of the Census, and some states use it to help encode driver’s license numbers. Your task is to convert a sequence of names into the corresponding Soundex codes.
A Soundex code always consists of a letter followed by three digits, such that:
1. The first letter of a name appears (unencoded) as the first character of the Soundex code, and is capitalized. It is also the only letter.
2. The letters ‘A’, ‘E’, ‘I’, ‘O’, ‘U’, ‘Y’, ‘W’ and ‘H’ are never encoded when they are not the first character in a word. They do serve, however, to break sequences of like-coded letters (see next rule).
3. All other letters are encoded according to the following table, except when they immediately follow a letter (including the first letter) that would be encoded with the same code digit, according to the table:
Code Key letters
1 B, P, F, V
2 C, S, K, G, J, Q, X, Z
3 D, T
4 L
5 M, N
6 R
4. Codes are truncated after the third digit.
5. Trailing zeros are appended as needed so all names are encoded with a letter followed by three digits.
The input contains a sequence of words in free format, and ends at end of file. The output written to the file should consist of a column of names and a column of their corresponding soundex codes in the format shown in the example below.
Example:
Input Output
LEE
Kuhne EBELL
ebelson
SCHAEFER
SCHAAK
LEE => L000
Kuhne => K500
EBELL => E140
ebelson => E142
SCHAEFER => S160
SCHAAK => S200


5. BIT
Crossbits are like Crosswords; instead of entering words you enter binary bits 01 in a Crossbit under certain given conditions, assuming that a solution exists. An empty Crossbit of size N is an empty grid of size N×N.
Given a natural number N , consider entering N2 binary bits in an empty Crossbit, satisfying the following conditions:

• Each square in the grid contains either a 0-bit or a 1-bit with no 1-bit in two major diagonals.
• The total number of 1-bit in each row / column is exactly equal to K , K being a given natural number less than N.
• A 0-bit has at least another adjacent 0-bit either in the same row or in the same column.
• The Crossbit represents the N2 -bit binary number B formed by placing bits in the 1st , the 2nd , ... the Nth row from left to right.

You are required to write a program that enters bits in an empty Crossbit so that the Crossbit represents the least binary number B for given N and K .
As an illustration consider the case with N = 4 and K = 1 . The Crossbit shown below represents the least binary number B = 0010100000010100 of 16 bits satisfying the specified conditions.
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
Input
The input may contain multiple test cases.
For each test case parameters N and K of the Crossbit are given in one line. Assume that N does not exceed 10.
The input terminates with a line containing 0 as input.
Output
For each test case, print the Crossbit in N rows; each row contains N bits with a space between two neighbouring bits. Keep a blank line after the last output line of each test case.
Example
Sample Input
4 1
6 2
0


Sample Output
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0


0 0 0 1 1 0
1 0 0 1 0 0
0 0 0 0 1 1
1 1 0 0 0 0
0 0 1 0 0 1
0 1 1 0 0 0




6. MATHEMATICAL EXPRESSION
You are to write a program to analyze some simple arithmetical expressions.
There must not be any semicolons ";" in your program!!!
Input
Multiple test cases, the number of them T is given in the very first line, T<=99.
Each test case contains one line with a correct expression, without leading or trailing spaces.
Output
For each test case you should output one line contains the result of the expression without any leading zeros. You may assume this number is always a non-negative one.
Example
Input:
3
6*7
67-25
31+11


Output:
42
42
42




7. RECTANGLES IN A SQUARE
You are employed by the designers of a modern EDA and you have been asked by your boss to solve one of the stages of the design process. More specifically, you are to present a piece of software which, given a square-shaped board and a list of rectangular semiconductor devices, tries to place them on the board. No element may lie outside the board (even partially) or overlap with another element.
You are rather vague about the details of your task, and so (surprisingly) is your boss. "Just make sure the guys from Marketing can feature <<Efficient Automated Semiconductor Placement>> in our sales brochure" -- he says, and leaves you to it.
Eventually, you decide to pack as many of the listed chips as possible on the given board (leaving out those that simply won't fit in), and go off for the evening to the local whisky bar, wondering whether the next recession in the technological cycle won't come sooner than in 5 years' time...
Input
t – number of test cases, then t tests follow. [t <= 500]
In the first line of each test there is an integer N, and in the second line an integer K. N is the length of the side of the square [2 <= N <= 1000], and K is the number of available rectangles [1 <= K <= 10000]. Then exactly K lines follow, with 3 numbers on each of them: wi, hi, li. wi - length of rectangle [wi <= N], hi - height of rectangle [hi <= N], li - number of rectangles of this type [li <= 200000]. You may rotate a rectangle by a multiple of 90 degrees.
Output
For each test case output integer R - number of used rectangles, and then exactly R lines. On each of these lines output integer coordinates of opposite corners of rectangle xi1, yi1, xi2, yi2. Solution will be accepted if all rectangles won't intersect with each other and won’t overrun the bounds of square.
Example
Input :
1
10
8
3 5 2
2 2 1
2 3 1
2 5 1
4 5 1
1 3 2
3 8 1
1 1 1
Output :
9
1 1 5 3
6 1 8 5
9 1 10 2
1 4 5 7
6 6 10 7
9 3 10 5
1 8 1 10
2 8 2 10
3 8 10 10