1. 
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: Problem H - Settlers of Catan
* Link: http://uva.onlinejudge.org/contests/240-0682ae4a/p7.html
*
* @author Dennis Wilfert
* @version 1.0, 11/17/2009
*
* Status : Accepted
* Runtime: 0,05s user 0,04s system
*/
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;

class Main {

public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));

// Werte mit Catan_precalc vorberechnet
int[] board = new int[]{1, 2, 3, 4, 5, 2, 3, 1, 4, 5, 1, 2, 3, 1, 4, 3, 5, 4, 2, 5, 2, 1, 3, 4, 5, 3, 1, 2, 4, 5, 1, 2, 4, 3, 1, 5, 3, 2, 4, 5, 2, 4, 1, 3, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 1, 5, 3, 5, 2, 4, 1, 3, 2, 4, 5, 2, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 2, 1, 5, 4, 3, 5, 2, 3, 4, 1, 5, 1, 3, 4, 5, 2, 3, 1, 2, 4, 5, 1, 2, 3, 4, 5, 3, 1, 2, 1, 4, 5, 2, 4, 3, 5, 3, 2, 1, 2, 5, 4, 1, 4, 5, 1, 3, 2, 3, 4, 5, 1, 2, 3, 4, 5, 3, 1, 2, 1, 4, 5, 4, 2, 3, 1, 2, 5, 3, 4, 5, 1, 2, 3, 5, 1, 4, 2, 4, 3, 5, 3, 1, 2, 5, 2, 1, 4, 3, 4, 5, 1, 2, 3, 4, 5, 3, 1, 2, 1, 4, 5, 3, 4, 5, 2, 1, 2, 3, 4, 5, 2, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 1, 2, 4, 3, 4, 5, 3, 1, 4, 5, 2, 1, 2, 5, 3, 4, 3, 1, 2, 1, 4, 2, 5, 3, 4, 5, 1, 2, 5, 3, 1, 4, 3, 4, 5, 2, 1, 3, 4, 5, 2, 3, 1, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 5, 3, 4, 2, 3, 1, 4, 5, 2, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 3, 4, 2, 5, 1, 2, 3, 4, 1, 5, 2, 3, 5, 1, 2, 4, 3, 4, 5, 1, 2, 3, 4, 5, 3, 1, 2, 4, 5, 1, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 4, 2, 5, 1, 4, 2, 3, 1, 3, 5, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 3, 1, 2, 1, 4, 5, 3, 5, 2, 4, 2, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 1, 4, 2, 3, 5, 4, 2, 4, 1, 3, 1, 5, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 5, 4, 1, 4, 2, 3, 2, 5, 1, 5, 3, 4, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 5, 2, 4, 1, 4, 3, 1, 5, 3, 2, 4, 5, 1, 2, 3, 4, 5, 3, 1, 2, 1, 4, 5, 4, 3, 2, 3, 5, 1, 2, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 1, 4, 2, 4, 5, 1, 3, 4, 2, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 5, 2, 4, 3, 1, 4, 2, 1, 5, 3, 1, 4, 5, 4, 2, 3, 1, 2, 5, 3, 4, 5, 1, 2, 5, 4, 1, 2, 3, 4, 3, 5, 2, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 1, 2, 4, 3, 4, 5, 1, 4, 2, 3, 5, 1, 2, 3, 4, 5, 1, 2, 5, 3, 4, 3, 1, 2, 1, 5, 4, 5, 2, 3, 1, 2, 5, 4, 3, 1, 4, 2, 4, 5, 3, 1, 2, 3, 4, 5, 2, 3, 1, 4, 5, 1, 2, 3, 4, 1, 5, 3, 4, 2, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 5, 3, 4, 2, 1, 4, 1, 3, 5, 4, 2, 3, 2, 5, 1, 3, 4, 5, 1, 2, 3, 4, 2, 1, 3, 4, 5, 2, 5, 1, 3, 1, 5, 4, 2, 3, 5, 1, 4, 2, 3, 4, 5, 1, 3, 4, 5, 2, 3, 1, 2, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 2, 3, 1, 4, 5, 1, 3, 2, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 5, 1, 4, 3, 2, 4, 5, 2, 3, 1, 5, 4, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 3, 1, 2, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 1, 4, 5, 4, 2, 3, 1, 5, 2, 5, 3, 4, 3, 1, 2, 1, 4, 2, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 4, 2, 5, 1, 2, 4, 5, 3, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 2, 3, 1, 5, 4, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 3, 1, 2, 1, 4, 5, 3, 5, 2, 4, 3, 1, 2, 1, 4, 5, 4, 3, 5, 2, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 5, 1, 3, 4, 2, 3, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 4, 2, 3, 1, 5, 2, 3, 1, 5, 4, 5, 2, 3, 2, 4, 1, 5, 3, 4, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 5, 4, 1, 3, 4, 3, 5, 2, 1, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 4, 2, 3, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 4, 3, 5, 2, 3, 1, 4, 5, 2, 1, 4, 5, 3, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 4, 5, 1, 2, 3, 4, 5, 1, 3, 4, 2, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 4, 2, 3, 2, 5, 1, 4, 1, 3, 5, 3, 2, 4, 2, 5, 1, 5, 3, 4, 3, 1, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 3, 4, 2, 5, 1, 3, 4, 2, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 4, 2, 3, 5, 1, 2, 3, 4, 5, 3, 1, 2, 1, 4, 5, 4, 3, 2, 3, 5, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 3, 1, 4, 5, 1, 2, 3, 5, 4, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 5, 4, 5, 1, 3, 4, 2, 5, 1, 3, 4, 3, 1, 2, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 4, 2, 3, 2, 5, 1, 5, 3, 4, 2, 1, 4, 1, 3, 5, 4, 2, 3, 1, 2, 5, 3, 4, 5, 1, 2, 5, 4, 1, 2, 3, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 4, 5, 3, 1, 2, 3, 4, 1, 2, 5, 3, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 5, 3, 2, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 4, 3, 5, 3, 1, 2, 1, 4, 5, 4, 2, 1, 3, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 5, 4, 1, 2, 3, 4, 5, 2, 3, 1, 4, 5, 1, 2, 3, 4, 1, 5, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 1, 2, 3, 5, 1, 4, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 2, 1, 5, 3, 1, 4, 5, 4, 2, 3, 2, 1, 5, 1, 3, 4, 5, 4, 2, 3, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 5, 3, 1, 2, 3, 4, 5, 1, 3, 4, 5, 2, 3, 1, 2, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 1, 4, 5, 2, 3, 4, 5, 1, 2, 5, 3, 4, 3, 1, 2, 1, 5, 4, 5, 2, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 3, 1, 5, 1, 4, 2, 4, 5, 3, 1, 2, 3, 4, 5, 3, 2, 4, 5, 1, 2, 1, 3, 4, 5, 2, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 3, 1, 2, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 4, 2, 3, 2, 5, 1, 5, 4, 3, 4, 1, 2, 3, 2, 5, 1, 4, 3, 1, 3, 5, 2, 1, 4, 5, 3, 4, 2, 5, 1, 2, 3, 4, 2, 1, 3, 4, 5, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 5, 3, 2, 3, 1, 5, 1, 4, 2, 3, 4, 5, 1, 2, 4, 3, 1, 2, 5, 3, 4, 5, 1, 3, 4, 5, 2, 3, 1, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 3, 1, 2, 1, 4, 5, 3, 5, 2, 4, 3, 1, 2, 1, 4, 5, 4, 3, 2, 3, 5, 1, 2, 1, 4, 5, 2, 3, 4, 5, 1, 2, 3, 1, 5, 2, 3, 4, 5, 4, 1, 2, 3, 5, 4, 2, 1, 3, 4, 5, 1, 2, 4, 5, 3, 1, 2, 3, 4, 5, 1, 3, 2, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 5, 2, 3, 4, 3, 1, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 3, 1, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 3, 2, 4, 2, 5, 1, 5, 3, 4, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 5, 4, 1, 2, 3, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 4, 5, 3, 1, 2, 3, 4, 1, 2, 5, 3, 4, 5, 1, 2, 3, 5, 1, 2, 4, 5, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 3, 1, 2, 1, 4, 5, 3, 5, 2, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 1, 5, 1, 3, 4, 5, 4, 2, 5, 3, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 5, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 1, 4, 2, 3, 1, 2, 5, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 3, 2, 4, 5, 1, 2, 1, 3, 4, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 5, 3, 4, 3, 1, 2, 5, 2, 4, 1, 5, 3, 4, 3, 1, 2, 1, 5, 4, 5, 2, 3, 4, 3, 1, 2, 1, 4, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 1, 4, 5, 2, 3, 1, 4, 5, 1, 2, 3, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 3, 2, 4, 2, 5, 1, 5, 3, 4, 1, 4, 2, 3, 2, 5, 1, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 2, 1, 3, 4, 5, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 4, 2, 5, 1, 3, 4, 5, 2, 3, 1, 2, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 4, 3, 5, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 3, 1, 4, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 2, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 3, 1, 2, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 1, 4, 5, 4, 2, 3, 2, 1, 5, 1, 3, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 5, 4, 5, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 5, 3, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 1, 4, 2, 3, 4, 5, 1, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 3, 1, 2, 1, 4, 5, 3, 5, 2, 4, 3, 1, 2, 1, 5, 4, 5, 2, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 1, 5, 4, 5, 3, 1, 2, 3, 4, 5, 3, 2, 4, 5, 1, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 2, 1, 3, 4, 5, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 3, 2, 1, 2, 5, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 2, 1, 3, 4, 5, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 3, 2, 1, 5, 1, 4, 2, 3, 4, 5, 1, 2, 4, 3, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 1, 5, 2, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 5, 3, 1, 2, 1, 4, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 5, 4, 3, 2, 3, 1, 4, 5, 1, 2, 3, 5, 1, 4, 2, 3, 4, 5, 1, 3, 2, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 2, 1, 3, 5, 1, 4, 5, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 4, 3, 5, 3, 1, 2, 1, 4, 5, 4, 3, 2, 3, 5, 1, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 4, 3, 5, 2, 3, 1, 2, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 4, 3, 2, 5, 1, 2, 3, 1, 4, 5, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 5, 4, 1, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 5, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 5, 4, 1, 2, 3, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 1, 5, 4, 2, 3, 4, 5, 3, 1, 2, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 4, 3, 1, 2, 5, 4, 2, 3, 1, 3, 5, 2, 1, 4, 5, 4, 2, 3, 2, 1, 5, 1, 3, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 5, 2, 4, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 2, 1, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 1, 5, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 1, 5, 3, 4, 2, 1, 4, 5, 3, 5, 2, 4, 3, 1, 2, 1, 5, 4, 5, 2, 3, 4, 3, 1, 2, 1, 5, 4, 5, 2, 3, 4, 3, 1, 2, 1, 4, 5, 2, 4, 5, 3, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 3, 2, 4, 5, 1, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 2, 1, 3, 5, 1, 5, 2, 4, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 4, 3, 1, 2, 5, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 2, 1, 3, 4, 5, 1, 5, 2, 3, 4, 2, 1, 3, 4, 5, 1, 5, 2, 3, 4, 5, 1, 3, 5, 2, 1, 4, 2, 3, 4, 5, 1, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 1, 2, 3, 4, 5, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 5, 2, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 2, 1, 3, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 2, 1, 2, 4, 5, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 2, 3, 1, 4, 5, 1, 2, 3, 5, 1, 4, 2, 3, 4, 5, 1, 3, 2, 5, 1, 4, 2, 3, 4, 5, 1, 3, 2, 5, 1, 4, 2, 3, 4, 5, 1, 2, 4, 1, 3, 5, 3, 2, 5, 4, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 4, 2, 3, 2, 1, 5, 1, 3, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 1, 5, 1, 3, 4, 5, 4, 2, 3, 2, 5, 1, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 4, 3, 5, 1, 2, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 5, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 2, 4, 1, 3, 1, 5, 3, 2, 5, 4, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 1, 4, 5, 4, 2, 3, 2, 1, 5, 1, 3, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 2, 1, 2, 4, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 2, 3, 4, 5, 3, 2, 4, 5, 1, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 3, 2, 4, 5, 1, 2, 1, 3, 4, 5, 1, 2, 3, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 5, 3, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 2, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 2, 4, 1, 5, 3, 1, 4, 3, 2, 5, 3, 1, 2, 1, 4, 5, 4, 3, 2, 3, 5, 1, 2, 1, 4, 5, 4, 2, 3, 2, 1, 5, 1, 3, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 3, 2, 4, 5, 1, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 4, 3, 5, 1, 2, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 3, 5, 2, 1, 4, 5, 2, 5, 3, 4, 3, 1, 2, 1, 5, 4, 5, 2, 3, 4, 3, 1, 2, 1, 5, 4, 5, 2, 3, 4, 3, 1, 2, 1, 5, 4, 5, 2, 3, 4, 1, 2, 3, 4, 1, 5, 2, 5, 4, 3, 1, 2, 3, 4, 5, 1, 2, 5, 4, 1, 2, 3, 4, 3, 5, 1, 2, 3, 4, 5, 3, 2, 4, 5, 1, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 5, 3, 1, 2, 3, 4, 5, 1, 2, 4, 3, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 2, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 4, 1, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 5, 4, 2, 1, 3, 4, 5, 1, 3, 4, 2, 5, 1, 2, 3, 4, 2, 1, 3, 4, 5, 1, 5, 2, 3, 4, 2, 1, 3, 4, 5, 1, 5, 2, 3, 4, 2, 1, 3, 4, 5, 1, 5, 3, 4, 2, 5, 2, 3, 1, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 5, 3, 4, 3, 1, 2, 1, 5, 4, 5, 2, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 4, 3, 4, 1, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 3, 4, 2, 5, 1, 2, 4, 5, 3, 1, 2, 3, 4, 5, 1, 3, 2, 5, 1, 4, 2, 3, 4, 5, 1, 3, 2, 5, 1, 4, 2, 3, 4, 5, 1, 3, 2, 5, 1, 4, 2, 4, 5, 3, 1, 3, 4, 5, 2, 3, 2, 4, 1, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 5, 4, 1, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 1, 4, 2, 3, 2, 5, 1, 3, 4, 5, 1, 2, 3, 4, 2, 1, 3, 4, 5, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 1, 5, 2, 3, 4, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 5, 3, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 1, 4, 5, 1, 3, 2, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 5, 1, 2, 4, 5, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 3, 1, 2, 1, 4, 5, 3, 2, 4, 2, 5, 1, 5, 3, 4, 3, 1, 2, 5, 4, 1, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 2, 5, 3, 4, 3, 1, 2, 1, 4, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 4, 5, 3, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 1, 4, 5, 1, 3, 2, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 5, 3, 4, 1, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 3, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 1, 4, 2, 3, 2, 5, 1, 5, 3, 4, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 1, 4, 5, 4, 3, 2, 3, 5, 1, 2, 4, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 5, 4, 5, 2, 3, 4, 3, 1, 2, 1, 5, 4, 5, 2, 3, 4, 3, 1, 2, 1, 4, 5, 3, 2, 1, 4, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 5, 3, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 5, 3, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 4, 2, 3, 2, 5, 1, 5, 4, 3, 4, 1, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 2, 3, 1, 4, 5, 1, 2, 5, 4, 1, 2, 3, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 2, 1, 3, 4, 5, 1, 5, 2, 3, 4, 2, 1, 3, 4, 5, 1, 5, 2, 3, 4, 5, 1, 2, 4, 3, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 4, 3, 5, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 4, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 2, 3, 4, 5, 1, 2, 3, 1, 5, 2, 3, 4, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 4, 2, 5, 1, 2, 3, 4, 1, 5, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 5, 1, 4, 2, 3, 4, 5, 1, 3, 2, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 1, 5, 2, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 3, 2, 3, 5, 1, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 4, 5, 3, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 4, 3, 5, 3, 1, 2, 1, 4, 5, 4, 2, 3, 1, 5, 2, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 4, 3, 4, 1, 2, 3, 2, 5, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 5, 4, 1, 2, 3, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 5, 4, 5, 2, 3, 4, 3, 1, 2, 1, 4, 5, 4, 3, 2, 3, 5, 1, 2, 1, 4, 2, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 1, 5, 2, 3, 4, 5, 4, 1, 2, 4, 5, 3, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 3, 1, 2, 1, 4, 5, 4, 3, 2, 3, 5, 1, 2, 1, 4, 5, 4, 3, 2, 3, 5, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 4, 3, 5, 3, 1, 2, 1, 4, 5, 4, 2, 3, 5, 3, 1, 2, 1, 4, 5, 4, 2, 5, 3, 2, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 2, 1, 3, 4, 5, 1, 5, 2, 3, 4, 5, 1, 2, 5, 4, 1, 2, 3, 4, 3, 5, 1, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 4, 5, 3, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 3, 2, 4, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 1, 2, 3, 4, 5, 1, 2, 5, 4, 1, 2, 3, 4, 3, 5, 1, 2, 5, 4, 1, 2, 3, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 1, 2, 5, 4, 5, 3, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 5, 2, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 5, 4, 1, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 1, 5, 1, 3, 4, 5, 4, 2, 3, 2, 5, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 3, 4, 2, 5, 1, 2, 3, 4, 1, 5, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 4, 5, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 4, 2, 3, 2, 5, 1, 5, 4, 3, 4, 1, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 3, 2, 3, 5, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 3, 2, 4, 5, 1, 2, 1, 3, 4, 5, 1, 2, 4, 5, 3, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 3, 1, 2, 1, 4, 5, 4, 3, 2, 3, 5, 1, 2, 1, 4, 5, 4, 2, 3, 2, 1, 5, 1, 3, 4, 5, 4, 2, 3, 2, 5, 1, 3, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 3, 2, 4, 2, 5, 3, 1, 4, 5, 1, 2, 3, 1, 5, 2, 3, 4, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 5, 4, 1, 2, 3, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 1, 4, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 3, 1, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 1, 2, 5, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 3, 2, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 4, 3, 4, 1, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 4, 5, 4, 2, 3, 2, 5, 1, 5, 3, 4, 3, 1, 2, 1, 5, 4, 5, 2, 3, 4, 3, 1, 2, 1, 4, 5, 4, 3, 2, 1, 2, 5, 3, 4, 5, 1, 2, 5, 4, 1, 2, 3, 4, 3, 5, 1, 2, 3, 4, 5, 3, 2, 4, 5, 1, 2, 1, 3, 4, 5, 1, 2, 4, 5, 3, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 4, 5, 3, 1, 2, 3, 4, 5, 2, 1, 4, 5, 3, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 3, 4, 2, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 2, 1, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 5, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 4, 3, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 5, 4, 1, 2};

for (int i = Integer.parseInt(reader.readLine()); i > 0; i--) {

// Wert an der Position des eingelesenen Wertes-1 ausgeben
writer.println(board[Integer.parseInt(reader.readLine()) - 1]);

}
writer.flush();

}
}




/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: Problem H - Settlers of Catan
* Link: http://uva.onlinejudge.org/contests/240-0682ae4a/p7.html
*
* @author Dennis Wilfert
* @version 1.0, 11/17/2009
*/
import java.util.Collections;
import java.util.LinkedList;

public class Catan_precalc {

static LinkedList<Values> val = new LinkedList<Values>();

public static void main(String[] args) {

Number[][] hex = new Number[3000][3000];

// Die möglichen Werte die in der Spirale stehen können
val.add(new Values(1));
val.add(new Values(2));
val.add(new Values(3));
val.add(new Values(4));
val.add(new Values(5));

Collections.sort(val);
Number tmp;
Number last;

// In der Mitte des Feldes mit der 1 beginnen
int x = 1500;
int y = 1500;
int a = 2;
int b = 1;

///// Die ersten 6 Werte eintragen /////
Number first = new Number();
first.value = val.get(0).num;
val.get(0).addCount();
last = first;
hex[x][y] = first;

x += 2;
y -= 1;

tmp = new Number();
tmp.value = val.get(1).num;
val.get(1).addCount();
last.m = tmp;
last = tmp;
hex[x][y] = tmp;

x -= 2;
y -= 1;

tmp = new Number();
tmp.value = val.get(2).num;
val.get(2).addCount();
last.m = tmp;
last = tmp;
hex[x][y] = tmp;

x -= 2;
y += 1;

tmp = new Number();
tmp.value = val.get(3).num;
val.get(3).addCount();
last.m = tmp;
last = tmp;
hex[x][y] = tmp;

y += 2;

tmp = new Number();
tmp.value = val.get(4).num;
val.get(4).addCount();
last.m = tmp;
last = tmp;
hex[x][y] = tmp;
Collections.sort(val);

x += 2;
y += 1;

tmp = new Number();
tmp.value = calcValue(x, y, hex);
Collections.sort(val);
last.m = tmp;
last = tmp;
hex[x][y] = tmp;
//////////////////////////////////////////


// Ab der dritten Reihe 57 weitere Umrundungen um den Mittelpunkt und
// dabei die korrektn Werte bestimmen und eintragen
for (int i = 0; i < 57; i++) {

a++;
b++;

for (int j = 1; j < a; j++) {
x = x + xCo();
y = y + yCo();

tmp = new Number();
// Einzutragenden Wert bestimmen und eintragen
tmp.value = calcValue(x, y, hex);
// Die Referenz zu diesem Objekt in das letzte eintragen
last.m = tmp;
last = tmp;
// In die Matrix eintragen
hex[x][y] = tmp;
// Liste neu sortieren
Collections.sort(val);
}
next();

for (int j = 1; j < b; j++) {
x = x + xCo();
y = y + yCo();
tmp = new Number();
tmp.value = calcValue(x, y, hex);
last.m = tmp;
last = tmp;
hex[x][y] = tmp;
Collections.sort(val);
}
next();

for (int k = 0; k < 4; k++) {
for (int j = 1; j < a; j++) {
x = x + xCo();
y = y + yCo();
tmp = new Number();
tmp.value = calcValue(x, y, hex);
last.m = tmp;
last = tmp;
hex[x][y] = tmp;
Collections.sort(val);
}
next();
}

}

// Verkettete Liste durchlaufen und die ersten 10000 Werte ausgeben
int t = 0;
Number temp = first;
while (t <= 10001) {
System.out.print(temp.value + ", ");
temp = temp.m;
t++;
}

}

// Sucht den Wert der ins aktuelle Feld eingetragen werden kann
static int calcValue(int x, int y, Number[][] hex) {

for (Values v : val) {
// Prüfen ob einer der Nachbarn bereiz den Wert v.num besitzt
if ((hex[x][y - 2] != null && hex[x][y - 2].value == v.num) || (hex[x - 2][y - 1] != null && hex[x - 2][y - 1].value == v.num) || (hex[x - 2][y + 1] != null && hex[x - 2][y + 1].value == v.num) || (hex[x][y + 2] != null && hex[x][y + 2].value == v.num) || (hex[x + 2][y + 1] != null && hex[x + 2][y + 1].value == v.num) || (hex[x + 2][y - 1] != null && hex[x + 2][y - 1].value == v.num)); // Hat keiner der Nachbarn diesen Wert, kann der Wert zurückgegeben werden
else {
v.addCount();
return v.num;
}

}
// Sollte niemals eintreten
return -1;

}

/**
* Gibt zurück um welchen Wert die x-und y-koordinaten erhöht/verringert werden
* müssen, um auf die nächste Position zu kommen.
*/

static int current = 5;

static int xCo() {

switch (current) {
case 0:
return 0;
case 1:
return -2;
case 2:
return -2;
case 3:
return 0;
case 4:
return 2;
case 5:
return 2;

}
// Sollte niemals eintreten
return 0;
}

static int yCo() {

switch (current) {
case 0:
return -2;
case 1:
return -1;
case 2:
return 1;
case 3:
return 2;
case 4:
return 1;
case 5:
return -1;

}
// Sollte niemals eintreten
return 0;
}

static void next() {
current++;
if (current == 6) {
current = 0;
}
}
}

/**
* Speichert eine der 5 Zahlen die vorkommen können und die bisherige Anzahl des
* Vorkommens dieser Zahl in der Spirale.
* Ist sortierbar nach den Kriterien aus der Aufgabe.
*
* Der erste Wert in der Liste ist immer der Wert der in die Spirale eingetragen werden kann,
* solange kein nacbar diesen Wert bereits besitzt
*/
class Values implements Comparable<Values> {

final int num;
private int counter = 0;

public Values(int n) {
num = n;
}

void addCount() {
counter++;
}

@Override
public int hashCode() {

return num;
}

@Override
public boolean equals(Object o) {

return num == o.hashCode();
}

public int compareTo(Values o) {

if (num < o.hashCode()) {
return counter <= o.counter ? -1 : 1;
} else {
return counter < o.counter ? -1 : 1;
}
}
}

/**
* Speichert den Wert des aktuellen Felds und die Referenz auf das
* nächste Number-Objekt (verkettete Liste)
*/
class Number {

int value;
Number m;
}