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()