{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cimg src\u003d\"CDN_BASE_URL/d37b8f74a1ac07badfe42aa484f8ebcb?v\u003d1714389486\" align\u003d\"right\"\u003eThe ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.\r\u003cbr\u003e— It is a matter of security to change such things every now and then, to keep the enemy in the dark.\r\u003cbr\u003e— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!\r\u003cbr\u003e— 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 on your office door.\r\u003cbr\u003e— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime!\r\u003cbr\u003e— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.\r\u003cbr\u003e— 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.\r\u003cbr\u003e\r\u003cbr\u003eNow, the minister of finance, who had been eavesdropping, intervened.\r\u003cbr\u003e— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound.\r\u003cbr\u003e— Hmm, in that case I need a computer program to minimize the cost. You don\u0027t know some very cheap software gurus, do you?\r\u003cbr\u003e— In fact, I do. You see, there is this programming contest going on... Help the prime minister 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.\r\u003cbr\u003e\u003cblockquote\u003e1033\u003cbr\u003e1733\u003cbr\u003e3733\u003cbr\u003e3739\u003cbr\u003e3779\u003cbr\u003e8779\u003cbr\u003e8179\u003c/blockquote\u003eThe 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."}},{"title":"Input","value":{"format":"HTML","content":"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)."}},{"title":"Output","value":{"format":"HTML","content":"One line for each case, either with a number stating the minimal cost or containing the word Impossible."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n1033 8179\r\n1373 8017\r\n1033 1033\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\r\n7\r\n0\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}