Build the Trinity Hall Prime Based on this challenge and this Math.SE question. Idea originally come from a Numberphile video. The goal is to reproduce the logic of Professor McKee when he builds this prime.
Your task is to build the Trinity Hall Prime, at a much lower scale. You are given a single number N greater than 2, representing the length of the prime we need.
Rules

N is decomposed into a rectangle W(idth) x H(eight). W and H must be close, so 12 is 4x3 and 16 is 4x4 with W &gt;= H
The first line got only 8's
The next lines have 8's in the outer and 1's in the middle
Each lines have 2 more 1's and 2 less 8's than the previous, except if W is odd, then the second line have only one 1 in the middle
Once you got your emblem, find the first prime greater than the emblem.
2 &lt;= N &lt;= 16
This is ascii-art, so newlines must be part of the output.
This is code-golf, so shortest code, in bytes, wins.

Test cases:
I   Emblem    O
================
2   88        89

3   888       907

4   88        88
    11        19

6   888       888
    818       827

8   8888      8888
    8118      8133

9   888       888
    818       818
    111       159

10  88888     88888
    88188     88213

16  8888      8888
    8118      8118
    1111      1111
    1111      1159
Python 3, 194 bytes



n=int(input())
R=range
w=n//max(i*(i*i&lt;=n&gt;1&gt;n%i)for i in R(1,n))
m=0
for i in R(n):m=m*10+1+7*(abs(i%w*2-w+1)//2*w&gt;i-w)
while any(m%p&lt;1for p in R(2,m)):m+=1
m=str(m)
while m:print(m[:w]);m=m[w:]


Try it online!

too slow for most inputs, especially x &gt; 8

-6 bytes thanks to Jonathan Frech
-98 bytes thanks to Leaky Nun