Fox Ciel is participating in a party in Prime Kingdom. There are n foxes there (include Fox Ciel). The i-th fox is ai years old.

They will have dinner around some round tables. You want to distribute foxes such that:

  1. Each fox is sitting at some table. 
  2. Each table has at least 3 foxes sitting around it. 
  3. The sum of ages of any two adjacent foxes around each table should be a prime number. 



If k foxes f1, f2, ..., fk are sitting around table in clockwise order, then for 1 ≤ i ≤ k - 1: fi and fi + 1 are adjacent, and f1 and fk are also adjacent.

If it is possible to distribute the foxes in the desired manner, find out a way to do that.

Input

The first line contains single integer n (3 ≤ n ≤ 200): the number of foxes in this party. 

The second line contains n integers ai (2 ≤ ai ≤ 104).

Output

If it is impossible to do this, output "Impossible".

Otherwise, in the first line output an integer m (<image>): the number of tables.

Then output m lines, each line should start with an integer k -=– the number of foxes around that table, and then k numbers — indices of fox sitting around that table in clockwise order.

If there are several possible arrangements, output any of them.

Examples

Input

4
3 4 8 9


Output

1
4 1 2 4 3


Input

5
2 2 2 2 2


Output

Impossible


Input

12
2 3 4 5 6 7 8 9 10 11 12 13


Output

1
12 1 2 3 6 5 12 9 8 7 10 11 4


Input

24
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25


Output

3
6 1 2 3 6 5 4
10 7 8 9 12 15 14 13 16 11 10
8 17 18 23 22 19 20 21 24

Note

In example 1, they can sit around one table, their ages are: 3-8-9-4, adjacent sums are: 11, 17, 13 and 7, all those integers are primes.

In example 2, it is not possible: the sum of 2+2 = 4 is not a prime number.

Difficulty: HARD
Tags: Flows and cuts

Starter code:

Solutions:
from collections import deque

class Dinic:

	def __init__(self, listEdge, s, t):
		self.s = s
		self.t = t
		self.graph = {}
		self.maxCap = 1000000
		for e in listEdge:
			if e[0] not in self.graph:
				self.graph[e[0]] = []
			if e[1] not in self.graph:
				self.graph[e[1]] = []
			self.graph[e[0]].append([e[1], e[2], len(self.graph[e[1]])])
			self.graph[e[1]].append([e[0], 0, len(self.graph[e[0]]) - 1])
		self.N = len(self.graph.keys())

	def bfs(self):
		self.dist = {}
		self.dist[self.s] = 0
		self.curIter = {node: [] for node in self.graph}
		Q = deque([self.s])
		while len(Q) > 0:
			cur = Q.popleft()
			for (index, e) in enumerate(self.graph[cur]):
				if e[1] > 0 and e[0] not in self.dist:
					self.dist[e[0]] = self.dist[cur] + 1
					self.curIter[cur].append(index)
					Q.append(e[0])

	def findPath(self, cur, f):
		if cur == self.t:
			return f
		while len(self.curIter[cur]) > 0:
			indexEdge = self.curIter[cur][-1]
			nextNode = self.graph[cur][indexEdge][0]
			remainCap = self.graph[cur][indexEdge][1]
			indexPreEdge = self.graph[cur][indexEdge][2]
			if remainCap > 0 and self.dist[nextNode] > self.dist[cur]:
				flow = self.findPath(nextNode, min(f, remainCap))
				if flow > 0:
					self.path.append(cur)
					self.graph[cur][indexEdge][1] -= flow
					self.graph[nextNode][indexPreEdge][1] += flow
					return flow
			self.curIter[cur].pop()
		return 0

	def maxFlow(self):
		maxflow = 0
		flow = []
		while True:
			self.bfs()
			if self.t not in self.dist:
				break
			while True:
				self.path = []
				f = self.findPath(self.s, self.maxCap)
				if f == 0:
					break
				flow.append(f)
				maxflow += f
		return maxflow

	def residualBfs(self):
		Q = deque([self.s])
		side = {self.s: 's'}
		while len(Q) > 0:
			cur = Q.popleft()
			for (index, e) in enumerate(self.graph[cur]):
				if e[1] > 0 and e[0] not in side:
					Q.append(e[0])
					side[e[0]] = 's'
		S = []
		T = []
		for x in self.graph:
			if x in side:
				S.append(x)
			else:
				T.append(x)
		return (set(S), set(T))

def push(G, u, v):
	if u not in G:
		G[u] = []
	if v not in G:
		G[v] = []
	G[u].append(v)
	G[v].append(u)

def bfs(u, used, G):
	(l, r) = (G[u][0], G[u][1])
	used[u] = 1
	used[l] = 1
	used[r] = 1
	S = [l, u, r]
	i = 2
	while i < len(S):
		cur = S[i]
		if cur in G:
			for v in G[cur]:
				if used[v] == 0:
					used[v] = 1
					S.append(v)
		i += 1
	return S
max_ = 20001
prime = [1] * max_
for i in range(2, max_):
	if prime[i] == 1:
		for j in range(2 * i, max_, i):
			prime[j] = 0
n = int(input())
a = list(map(int, input().split()))
diff = 0
for x in a:
	if x % 2 == 0:
		diff += 1
	else:
		diff -= 1
flg = True
if diff != 0:
	flg = False
else:
	edge = []
	for i in range(n):
		if a[i] % 2 == 1:
			edge.append([i, 't', 2])
			continue
		edge.append(['s', i, 2])
		for j in range(n):
			if a[j] % 2 == 1 and prime[a[i] + a[j]] == 1:
				edge.append([i, j, 1])
	g = Dinic(edge, 's', 't')
	F = g.maxFlow()
	if F != n:
		flg = False
	else:
		G = {}
		for (u, es) in g.graph.items():
			if u in ['s', 't'] or a[u] % 2 == 1:
				continue
			for e in es:
				(v, remain) = (e[0], e[1])
				if isinstance(v, int) == True and remain == 0:
					push(G, u, v)
		used = [0] * n
		comp = []
		for i in range(n):
			if a[i] % 2 == 0 and used[i] == 0:
				comp.append(bfs(i, used, G))
if flg == False:
	print('Impossible')
else:
	print(len(comp))
	for nodes in comp:
		for i in range(len(nodes)):
			nodes[i] += 1
		arr = [len(nodes)] + nodes
		print(' '.join([str(x) for x in arr]))


def main():
	sieve = [False, True] * 10001
	for i in range(3, 140, 2):
		if sieve[i]:
			(j, k) = (i * 2, i * i)
			le = (20001 - k) // j + 1
			sieve[k::j] = [False] * le
	n = int(input())
	aa = list(map(int, input().split()))
	pp = [-1] * n

	def dsu_get(v):
		if dsu[v] != v:
			dsu[v] = dsu_get(dsu[v])
		return dsu[v]

	def dfs(v):
		if free[v]:
			(free[v], a, pv) = (False, aa[v], pp[v])
			for (i, p) in enumerate(pp):
				if sieve[a + aa[i]] and pv != i and (p == -1 or dfs(p)):
					pp[i] = v
					return True
		return False
	for i in range(n):
		free = [True] * n
		if not dfs(i):
			print('Impossible')
			return
	dsu = list(range(n))
	for (i, p) in enumerate(pp):
		(i, p) = (dsu_get(i), dsu_get(p))
		dsu[p] = i
	print(sum((dsu_get(i) == i for i in range(n))))
	for i in range(n):
		if dsu_get(i) == i:
			row = [sum((dsu_get(j) == i for j in range(n))), i + 1]
			j = pp[i]
			while j != i:
				row.append(j + 1)
				j = pp[j]
			print(*row)
main()


N = int(input())
L = list(map(int, input().split(' ')))

def isPrime(x):
	for i in range(2, int(x ** 0.5) + 2):
		if x % i == 0:
			return False
	return True
odd = []
even = []
for i in range(N):
	if L[i] % 2 == 0:
		even.append(i)
	else:
		odd.append(i)
if len(odd) != len(even):
	print('Impossible')
	exit()
cap = [[0] * (N + 2) for i in range(N + 2)]
for i in odd:
	cap[N][i] = 2
for i in even:
	cap[i][N + 1] = 2
for i in odd:
	for j in even:
		if isPrime(L[i] + L[j]):
			cap[i][j] = 1

def send(x, flow):
	global visited, N
	if x == N + 1 or flow == 0:
		return flow
	visited[x] = True
	ret = 0
	for nxt in range(N + 2):
		if visited[nxt]:
			continue
		if cap[x][nxt] == 0:
			continue
		n_flow = min(cap[x][nxt], flow)
		n_flow = send(nxt, n_flow)
		flow -= n_flow
		ret += n_flow
		cap[x][nxt] -= n_flow
		cap[nxt][x] += n_flow
	return ret
flow = 0
while True:
	visited = [False] * (N + 2)
	f = send(N, N)
	if f == 0:
		break
	flow += f
if flow != N:
	print('Impossible')
	exit()

def dfs(x, path):
	global visited, N, edge
	visited[x] = True
	ret = 1
	path.append(x)
	for nxt in edge[x]:
		if visited[nxt]:
			continue
		ret += dfs(nxt, path)
	return ret
visited = [False] * N
edge = [[] for i in range(N)]
for i in odd:
	for j in even:
		if cap[j][i] == 1:
			edge[i].append(j)
			edge[j].append(i)
cnt = []
ans = []
for i in range(N):
	if visited[i] == True:
		continue
	ans.append([])
	cnt.append(dfs(i, ans[-1]))
print(len(cnt))
for i in range(len(cnt)):
	print(cnt[i], end=' ')
	for j in ans[i]:
		print(j + 1, end=' ')
	print()


import math

def ip(x):
	for i in range(2, 1 + int(math.sqrt(x))):
		if not x % i:
			return False
	return True

def add(x, y, z):
	cap[x][y] = z

def send(x, flow):
	if x == n + 1:
		return flow
	if vis[x]:
		return 0
	vis[x] = 1
	ret = 0
	for i in range(n + 2):
		if cap[x][i]:
			tmp = send(i, min(cap[x][i], flow))
			ret += tmp
			cap[x][i] -= tmp
			cap[i][x] += tmp
			flow -= tmp
			if not flow:
				return ret
	return ret

def flow():
	global vis
	ret = 0
	while True:
		vis = [0 for i in range(n + 2)]
		tmp = send(n, n)
		ret += tmp
		if not tmp:
			break
	return ret
n = int(input())
a = [int(x) for x in input().split()]
odd = [1 if x % 2 else 0 for x in a]
even = [0 if x % 2 else 1 for x in a]
cap = [[0 for i in range(n + 2)] for j in range(n + 2)]
w = [[0 for i in range(n + 2)] for j in range(n + 2)]
if sum(odd) - sum(even):
	print('Impossible')
	exit()
for i in range(n):
	if odd[i]:
		add(n, i, 2)
		for j in range(n):
			if ip(a[i] + a[j]):
				add(i, j, 1)
	else:
		add(i, n + 1, 2)
if flow() == n:
	for i in range(n):
		for j in range(n):
			if odd[i] and cap[j][i]:
				w[i][j] = 1
				w[j][i] = 1
	ans = []
	vis = [0 for i in range(n)]
	for i in range(n):
		if not vis[i]:
			cur = i
			ans.append([])
			while not vis[cur]:
				ans[-1].append(cur + 1)
				vis[cur] = 1
				for j in range(n):
					if w[cur][j] and (not vis[j]):
						cur = j
						break
	print(len(ans))
	for x in ans:
		print('%d %s' % (len(x), ' '.join([str(_) for _ in x])))
else:
	print('Impossible')