On the Fence

Πρόσφατα κληρονομήσατε ένα όμορφο οικόπεδο, το οποίο μπορεί να αναπαρασταθεί ως ένα πλέγμα με ~N~ γραμμές και ~M~ στήλες. Τώρα θέλετε να προστατεύσετε τη γη σας από εισβολείς, κατασκευάζοντας έναν τεράστιο φράχτη πάνω σε αυτήν.

Θα κατασκευάσετε αυτόν τον φράχτη επιλέγοντας έως και ~K~ κελιά του πλέγματος και γεμίζοντας καθένα από αυτά με ένα τσιμεντένιο μπλοκ. Αυτά τα κελιά αποτελούν τον φράχτη.

Λόγω μυστηριωδών κατασκευαστικών νόμων, το κελί στη γραμμή ~R~ και τη στήλη ~C~ πρέπει να ανήκει στον φράχτη.

Επιπλέον, τα κελιά του φράχτη πρέπει να σχηματίζουν ένα ενιαίο συνεκτικό τμήμα - θα πρέπει να μπορείτε να μετακινηθείτε από οποιοδήποτε κελί του φράχτη σε οποιοδήποτε άλλο, κινούμενοι μόνο κατακόρυφα ή οριζόντια (όχι διαγώνια) και περνώντας μόνο από κελιά του φράχτη.

Τα κελιά που βρίσκονται στη γραμμή ~1~, στη στήλη ~1~, στη γραμμή ~N~ ή στη στήλη ~M~ ονομάζονται κελιά των άκρων.

Ένα κελί που δεν ανήκει στον φράχτη βρίσκεται έξω από τον φράχτη αν μπορείτε να μετακινηθείτε από αυτό το κελί σε κάποιο κελί των άκρων, κινούμενοι κατακόρυφα, οριζόντια ή διαγώνια, χωρίς να περάσετε μέσα από κανένα κελί του φράχτη.

Σε διαφορετική περίπτωση, το κελί βρίσκεται μέσα στον φράχτη.

Η παρακάτω εικόνες δείχνουν μερικά παραδείγματα έγκυρων και μη έγκυρων φραχτών.

Αυτός είναι ένας έγκυρος φράχτης που αποτελείται από ~17~ μπλοκ και περικλείει ~5~ εσωτερικά κελιά.

Ο φράχτης αυτός δεν είναι έγκυρος, επειδή δεν είναι συνεκτικός.

Αυτός ο φράχτης είναι έγκυρος, αλλά περικλείει ~0~ εσωτερικά κελιά.

Θέλετε να προστατεύσετε όσο το δυνατόν μεγαλύτερο μέρος της γης σας. Βρείτε τον μέγιστο αριθμό εσωτερικών κελιών που μπορείτε να περικλείσετε μέσα στον φράχτη σας.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει έναν ακέραιο ~T~, τον αριθμό των περιπτώσεων ελέγχου στην είσοδο.

Οι επόμενες ~T~ γραμμές περιέχουν από μία περίπτωση ελέγχου, αποτελούμενη από πέντε ακεραίους ~N~, ~M~, ~K~, ~R~ και ~C~, χωρισμένους με κενά (~1 \le K \le NM~, ~1 \le R \le N~, ~1 \le C \le M~).

Ο παρακάτω πίνακας δείχνει πώς κατανέμονται οι ~15~ διαθέσιμοι βαθμοί:

Βαθμοί	Όρια του ~T~	Όρια των ~N,M~	Επιπλέον Περιορισμοί
~1~	~T \le 1000~	~1 \le N,M \le 10^9~	~K = NM~
~2~	~T \le 10~	~1 \le N,M \le 6~	Κανένας.
~2~	~T \le 10~	~1 \le N,M \le 40~	Κανένας
~2~	~T \le 10~	~1 \le N,M \le 300~	Κανένας.
~2~	~T \le 10~	~1 \le N,M \le 2000~	Κανένας.
~3~	~T \le 10~	~1 \le N,M \le 10^6~	Κανένας.
~3~	~T \le 1000~	~1 \le N,M \le 10^9~	Κανένας.

Έξοδος

Εκτυπώστε ~T~ γραμμές. Η ~t~-οστή γραμμή πρέπει να περιέχει έναν ακέραιο, την απάντηση για την ~t~-οστή περίπτωση ελέγχου.

Παραδείγματα

input

2
5 6 12 3 4
3 6 18 2 4

output

4
3

Επεξήγηση του παραδείγματος:

Παρακάτω φαίνονται οι βέλτιστοι φράχτες για τις δύο περιπτώσεις ελέγχου, οι οποίοι περικλείουν αντίστοιχα ~4~ και ~3~ εσωτερικά κελιά.