A set of four prime numbers arranged like (a, a + 2, a + 6, a + 8) is called a quadruplet prime number. Of the four prime numbers that make up a quadruplet prime, the largest number is called the size of the quadruplet prime. For example, the smallest prime quadruplet is a set of (5, 7, 11, 13), which is 13 in size. The next largest prime quadruplet is the set of (11, 13, 17, 19), which is 19 in size.

Create a program that takes the integer n (13 ≤ n ≤ 10,000,000) as input and outputs the maximum size of the quadruplet prime numbers whose size is n or less.



Input

A sequence of multiple datasets is given as input. The end of the input is indicated by a single line of zeros. One integer n is given on one row for each dataset.

The number of datasets does not exceed 2000.

Output

Outputs the maximum prime quadruplet size on one line for each input dataset.

Example

Input

13
14
15
16
17
18
19
20
10000
0


Output

13
13
13
13
13
13
19
19
9439

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
MAX = 899
diff = (0, 3, 3, 21, 22, 13, 7, 39, 7, 73, 126, 119, 88, 3, 11, 66, 29, 17, 53, 42, 101, 214, 104, 298, 252, 133, 255, 141, 76, 91, 168, 81, 45, 56, 203, 301, 43, 66, 291, 223, 92, 97, 442, 290, 437, 281, 38, 144, 549, 241, 29, 192, 11, 518, 266, 490, 122, 130, 13, 329, 85, 209, 71, 241, 290, 18, 301, 52, 120, 34, 50, 805, 276, 217, 182, 53, 209, 155, 77, 468, 448, 29, 90, 85, 91, 7, 146, 21, 309, 234, 60, 213, 511, 59, 273, 364, 57, 77, 87, 231, 452, 168, 154, 346, 273, 588, 11, 91, 322, 335, 140, 221, 87, 442, 297, 95, 321, 498, 146, 182, 8, 38, 11, 679, 111, 120, 83, 36, 59, 462, 32, 349, 448, 333, 644, 63, 101, 960, 161, 759, 255, 354, 270, 52, 200, 133, 112, 297, 298, 27, 74, 577, 25, 182, 280, 584, 756, 266, 287, 277, 119, 31, 561, 59, 179, 630, 34, 98, 1, 84, 217, 234, 4, 48, 127, 528, 679, 35, 108, 15, 752, 60, 31, 228, 559, 7, 35, 56, 43, 10, 151, 374, 297, 294, 14, 60, 196, 133, 18, 63, 63, 17, 35, 290, 953, 584, 66, 102, 427, 4, 357, 507, 441, 420, 802, 14, 66, 171, 252, 88, 14, 364, 32, 220, 66, 256, 427, 651, 52, 287, 987, 214, 161, 319, 241, 1333, 190, 325, 63, 500, 1026, 60, 13, 112, 238, 144, 137, 349, 417, 32, 164, 196, 115, 735, 200, 382, 273, 104, 119, 214, 665, 235, 297, 665, 25, 34, 211, 280, 542, 375, 188, 42, 134, 573, 350, 106, 17, 112, 676, 1095, 403, 62, 193, 60, 13, 116, 60, 255, 609, 350, 7, 165, 661, 25, 748, 176, 10, 283, 144, 987, 389, 59, 60, 342, 112, 144, 31, 98, 676, 297, 652, 189, 56, 34, 441, 50, 314, 266, 29, 546, 297, 39, 657, 46, 703, 70, 270, 221, 122, 767, 13, 134, 318, 1222, 84, 650, 371, 92, 164, 760, 318, 175, 158, 679, 496, 389, 273, 38, 676, 270, 902, 228, 143, 196, 18, 287, 102, 409, 612, 1, 56, 269, 311, 714, 1092, 176, 34, 165, 143, 438, 266, 249, 97, 442, 105, 7, 913, 81, 80, 871, 497, 585, 574, 11, 220, 94, 855, 132, 473, 836, 301, 7, 833, 63, 1145, 60, 1886, 382, 111, 43, 111, 319, 431, 108, 297, 60, 878, 799, 133, 472, 529, 420, 241, 46, 231, 304, 616, 1145, 595, 447, 589, 76, 399, 865, 154, 101, 119, 739, 528, 673, 49, 994, 412, 1072, 6, 25, 3, 49, 126, 1079, 1141, 66, 220, 932, 1049, 561, 692, 764, 476, 248, 200, 1897, 658, 644, 24, 399, 143, 1331, 839, 1, 1077, 760, 11, 34, 658, 36, 647, 21, 528, 242, 98, 529, 24, 1117, 192, 396, 930, 224, 365, 66, 557, 377, 757, 322, 203, 335, 770, 155, 97, 21, 665, 484, 553, 321, 207, 116, 574, 272, 287, 253, 637, 259, 38, 263, 62, 1268, 451, 693, 756, 630, 357, 105, 32, 581, 455, 153, 540, 350, 91, 210, 409, 270, 377, 442, 490, 615, 424, 52, 890, 199, 102, 1746, 462, 749, 24, 644, 540, 220, 840, 1656, 223, 74, 434, 179, 665, 923, 428, 307, 875, 50, 2387, 276, 109, 363, 529, 550, 139, 798, 176, 150, 297, 123, 66, 266, 414, 17, 130, 1344, 300, 1799, 8, 1176, 279, 351, 461, 396, 112, 626, 498, 931, 2782, 123, 1253, 780, 781, 1119, 46, 39, 847, 468, 1037, 1144, 63, 332, 294, 1082, 525, 459, 220, 70, 231, 31, 1029, 256, 290, 662, 242, 98, 252, 13, 1008, 64, 346, 1211, 119, 802, 189, 272, 298, 122, 697, 319, 195, 273, 410, 1221, 365, 885, 322, 52, 847, 165, 112, 67, 812, 630, 801, 87, 60, 424, 630, 867, 231, 123, 308, 396, 76, 119, 60, 203, 17, 63, 553, 931, 147, 588, 127, 437, 164, 43, 14, 371, 115, 150, 354, 315, 473, 3, 1221, 245, 36, 272, 214, 24, 385, 249, 182, 445, 171, 35, 921, 300, 1558, 1250, 129, 539, 476, 94, 11, 227, 427, 151, 102, 126, 2176, 71, 297, 60, 413, 195, 190, 944, 49, 554, 1102, 676, 279, 78, 143, 364, 357, 462, 1144, 1050, 218, 423, 623, 364, 416, 239, 143, 280, 248, 365, 77, 77, 1529, 157, 361, 514, 536, 31, 330, 87, 193, 514, 935, 227, 18, 91, 104, 49, 133, 1149, 104, 518, 396, 1015, 143, 445, 360, 385, 680, 49, 1053, 669, 647, 931, 140, 231, 31, 1075, 483, 627, 101, 1012, 714, 346, 504, 60, 917, 1140, 1180, 98, 297, 1029, 225, 1918, 406, 188, 368, 466, 1305, 1117, 1028, 50, 150, 273, 333, 101, 151, 146, 1100, 119, 1532, 497, 487, 235, 658, 322, 538, 210, 701, 574, 136, 220, 168, 105, 603, 332, 409, 84, 81, 39, 860, 309, 384, 259, 266, 207, 872, 377, 403, 248, 819, 882, 931, 148, 42, 371, 805, 325, 668, 529, 409, 3151, 2016, 14, 38, 1487, 350, 295, 266, 343, 1833, 1887, 123, 370, 260, 696, 137, 962, 410, 132, 847, 1051, 426, 39, 214, 546, 539, 493, 325, 137, 112, 889, 130, 237, 43, 1183, 118, 371, 1, 580, 316, 434, 2698, 53, 98, 262, 203, 119, 31, 189, 813, 119, 195, 294, 1435, 1345, 531, 624, 210, 231, 321, 553, 11, 756, 1358)

def bsch(x):
	(l, r) = (0, MAX)
	while l < r:
		m = l + r >> 1
		if tbl[m] == x:
			return m
		if tbl[m] < x:
			l = m + 1
		else:
			r = m
	return l - 1
tbl = [0] * MAX
for i in range(1, MAX):
	tbl[i] = tbl[i - 1] + diff[i]
for i in range(MAX):
	tbl[i] = tbl[i] * 30 + 19
while 1:
	n = int(input())
	if n == 0:
		break
	if n < 19:
		print('13')
	else:
		print(tbl[bsch(n)])


MAX = 899
diff = (0, 3, 3, 21, 22, 13, 7, 39, 7, 73, 126, 119, 88, 3, 11, 66, 29, 17, 53, 42, 101, 214, 104, 298, 252, 133, 255, 141, 76, 91, 168, 81, 45, 56, 203, 301, 43, 66, 291, 223, 92, 97, 442, 290, 437, 281, 38, 144, 549, 241, 29, 192, 11, 518, 266, 490, 122, 130, 13, 329, 85, 209, 71, 241, 290, 18, 301, 52, 120, 34, 50, 805, 276, 217, 182, 53, 209, 155, 77, 468, 448, 29, 90, 85, 91, 7, 146, 21, 309, 234, 60, 213, 511, 59, 273, 364, 57, 77, 87, 231, 452, 168, 154, 346, 273, 588, 11, 91, 322, 335, 140, 221, 87, 442, 297, 95, 321, 498, 146, 182, 8, 38, 11, 679, 111, 120, 83, 36, 59, 462, 32, 349, 448, 333, 644, 63, 101, 960, 161, 759, 255, 354, 270, 52, 200, 133, 112, 297, 298, 27, 74, 577, 25, 182, 280, 584, 756, 266, 287, 277, 119, 31, 561, 59, 179, 630, 34, 98, 1, 84, 217, 234, 4, 48, 127, 528, 679, 35, 108, 15, 752, 60, 31, 228, 559, 7, 35, 56, 43, 10, 151, 374, 297, 294, 14, 60, 196, 133, 18, 63, 63, 17, 35, 290, 953, 584, 66, 102, 427, 4, 357, 507, 441, 420, 802, 14, 66, 171, 252, 88, 14, 364, 32, 220, 66, 256, 427, 651, 52, 287, 987, 214, 161, 319, 241, 1333, 190, 325, 63, 500, 1026, 60, 13, 112, 238, 144, 137, 349, 417, 32, 164, 196, 115, 735, 200, 382, 273, 104, 119, 214, 665, 235, 297, 665, 25, 34, 211, 280, 542, 375, 188, 42, 134, 573, 350, 106, 17, 112, 676, 1095, 403, 62, 193, 60, 13, 116, 60, 255, 609, 350, 7, 165, 661, 25, 748, 176, 10, 283, 144, 987, 389, 59, 60, 342, 112, 144, 31, 98, 676, 297, 652, 189, 56, 34, 441, 50, 314, 266, 29, 546, 297, 39, 657, 46, 703, 70, 270, 221, 122, 767, 13, 134, 318, 1222, 84, 650, 371, 92, 164, 760, 318, 175, 158, 679, 496, 389, 273, 38, 676, 270, 902, 228, 143, 196, 18, 287, 102, 409, 612, 1, 56, 269, 311, 714, 1092, 176, 34, 165, 143, 438, 266, 249, 97, 442, 105, 7, 913, 81, 80, 871, 497, 585, 574, 11, 220, 94, 855, 132, 473, 836, 301, 7, 833, 63, 1145, 60, 1886, 382, 111, 43, 111, 319, 431, 108, 297, 60, 878, 799, 133, 472, 529, 420, 241, 46, 231, 304, 616, 1145, 595, 447, 589, 76, 399, 865, 154, 101, 119, 739, 528, 673, 49, 994, 412, 1072, 6, 25, 3, 49, 126, 1079, 1141, 66, 220, 932, 1049, 561, 692, 764, 476, 248, 200, 1897, 658, 644, 24, 399, 143, 1331, 839, 1, 1077, 760, 11, 34, 658, 36, 647, 21, 528, 242, 98, 529, 24, 1117, 192, 396, 930, 224, 365, 66, 557, 377, 757, 322, 203, 335, 770, 155, 97, 21, 665, 484, 553, 321, 207, 116, 574, 272, 287, 253, 637, 259, 38, 263, 62, 1268, 451, 693, 756, 630, 357, 105, 32, 581, 455, 153, 540, 350, 91, 210, 409, 270, 377, 442, 490, 615, 424, 52, 890, 199, 102, 1746, 462, 749, 24, 644, 540, 220, 840, 1656, 223, 74, 434, 179, 665, 923, 428, 307, 875, 50, 2387, 276, 109, 363, 529, 550, 139, 798, 176, 150, 297, 123, 66, 266, 414, 17, 130, 1344, 300, 1799, 8, 1176, 279, 351, 461, 396, 112, 626, 498, 931, 2782, 123, 1253, 780, 781, 1119, 46, 39, 847, 468, 1037, 1144, 63, 332, 294, 1082, 525, 459, 220, 70, 231, 31, 1029, 256, 290, 662, 242, 98, 252, 13, 1008, 64, 346, 1211, 119, 802, 189, 272, 298, 122, 697, 319, 195, 273, 410, 1221, 365, 885, 322, 52, 847, 165, 112, 67, 812, 630, 801, 87, 60, 424, 630, 867, 231, 123, 308, 396, 76, 119, 60, 203, 17, 63, 553, 931, 147, 588, 127, 437, 164, 43, 14, 371, 115, 150, 354, 315, 473, 3, 1221, 245, 36, 272, 214, 24, 385, 249, 182, 445, 171, 35, 921, 300, 1558, 1250, 129, 539, 476, 94, 11, 227, 427, 151, 102, 126, 2176, 71, 297, 60, 413, 195, 190, 944, 49, 554, 1102, 676, 279, 78, 143, 364, 357, 462, 1144, 1050, 218, 423, 623, 364, 416, 239, 143, 280, 248, 365, 77, 77, 1529, 157, 361, 514, 536, 31, 330, 87, 193, 514, 935, 227, 18, 91, 104, 49, 133, 1149, 104, 518, 396, 1015, 143, 445, 360, 385, 680, 49, 1053, 669, 647, 931, 140, 231, 31, 1075, 483, 627, 101, 1012, 714, 346, 504, 60, 917, 1140, 1180, 98, 297, 1029, 225, 1918, 406, 188, 368, 466, 1305, 1117, 1028, 50, 150, 273, 333, 101, 151, 146, 1100, 119, 1532, 497, 487, 235, 658, 322, 538, 210, 701, 574, 136, 220, 168, 105, 603, 332, 409, 84, 81, 39, 860, 309, 384, 259, 266, 207, 872, 377, 403, 248, 819, 882, 931, 148, 42, 371, 805, 325, 668, 529, 409, 3151, 2016, 14, 38, 1487, 350, 295, 266, 343, 1833, 1887, 123, 370, 260, 696, 137, 962, 410, 132, 847, 1051, 426, 39, 214, 546, 539, 493, 325, 137, 112, 889, 130, 237, 43, 1183, 118, 371, 1, 580, 316, 434, 2698, 53, 98, 262, 203, 119, 31, 189, 813, 119, 195, 294, 1435, 1345, 531, 624, 210, 231, 321, 553, 11, 756, 1358)
import bisect
tbl = [0] * MAX
for i in range(1, MAX):
	tbl[i] = tbl[i - 1] + diff[i]
for i in range(MAX):
	tbl[i] = tbl[i] * 30 + 19
while 1:
	n = int(input())
	if n == 0:
		break
	if n < 19:
		print('13')
	else:
		p = bisect.bisect_left(tbl, n)
		if tbl[p] == n:
			print(n)
		else:
			print(tbl[p - 1])