D. Номер перестановки

Все перестановки чисел от 1 до $n$ выписаны в лексикографическом порядке и пронумерованы с нуля. По перестановке найдите её номер.

В первой строке $q$ ($1 \le q \le 10^4$). В каждой из следующих $q$ строк — число $n$ ($1 \le n \le 18$) и затем $n$ чисел: перестановка чисел от 1 до $n$.

Для каждого запроса выведите номер перестановки в отдельной строке.