#P5449. 序列

    ID: 4455 传统题 4000ms 256MiB 尝试: 82 已通过: 30 难度: 7 上传者: 标签>CF2200提高IDA*可采纳估价函数估价下界剪枝搜索顺序优化回溯搜索添加哨兵增量维护

序列

Description

一个1~n的排列x,每次你可以将x1~xi翻转。

你需要求出将序列变为升序的最小操作次数。

有多组数据。

Format

Input

第一行一个整数t表示数据组数。

每组数据第一行一个整数n,第二行n个整数

x1~xn。

t=5,n<=25

Output

每组数据输出一行一个整数表示答案。

Samples

1
8
8 6 1 3 2 4 5 7
7